对称二叉树-leetcode

题目描述

• 给你一个二叉树的根节点 root ， 检查它是否轴对称。

  示例 1：

  

  输入：root = [1,2,2,3,4,4,3]
  输出：true
  

  示例 2：

  

  输入：root = [1,2,2,null,3,null,3]
  输出：false
  

  提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

解法一

思路：

深度优先搜索+递归

两棵树镜像对称，根1，2节点相同外，根节点1的左子树与根节点2右子树镜像对称，根节点1的左子树与根节点2右子树镜像对称。

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean dfs(TreeNode root1,TreeNode root2) {//根节点都为空，镜像对称if(root1==null&&root2==null) return true;//根节点有一个不为空，不是镜像对称if(root1==null||root2==null) return false;//都不为空，判断节点值是否相同，左子树与右子树是否镜像对称，右子树与左子树是否镜像对称return (root1.val==root2.val)&&dfs(root1.left,root2.right) &&dfs(root1.right,root2.left);}public boolean isSymmetric(TreeNode root) {return dfs(root,root);}
}

解法二

思路：

广度优先搜索+队列

两棵树镜像对称，根1，2节点相同外，根1的左节点与根2的右节点相同，根1的右节点与根2的左节点相同。

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.add(root);queue.add(root);while(!queue.isEmpty()) {TreeNode t1 = queue.poll();TreeNode t2 = queue.poll();if(t1 == null && t2 == null) continue;if(t1 == null || t2 == null) return false;if(t1.val != t2.val) return false;queue.add(t1.left);queue.add(t2.right);queue.add(t1.right);queue.add(t2.left);}return true;}
}