判断一棵二叉树是否为对称的树。如
1
/ \
2 2
/ \ / \
3 4 4 3
观察上面的树可以看出：左子树的右子树等于右子树的左子树，左子树的左子树等于右子树的右子树。
首先可以使用递归。递归容易理解
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return isSym(root.left,root.right);
}
public boolean isSym(TreeNode node1,TreeNode node2){
if(node1==null&&node2==null) return true;
if(node1==null||node2==null) return false;
if(node1.val!=node2.val) return false;
return isSym(node1.left,node2.right)&&isSym(node1.right,node2.left);
}
}
再是可以使用迭代，不用递归。
思路就是向遍历一样，每一层比较，但是不输出，只是在遍历过程中比较。使用广度优先遍历。因为要比较，所以一次取出两个节点，进行比较。然后存放时，因为需要比较的是a节点的左子树跟b节点的右子树，a节点的右子树和b节点的左子树。所以存放时也按照这种顺序存放进队列，方便取出两个时直接比较。见代码
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> q=new LinkedList<>();
//先存入两个节点，用于比较
q.add(root.left);
q.add(root.right);
while(q.size()>0){
TreeNode left=q.poll();
TreeNode right=q.poll();
if(left==null&&right==null) continue;//由于可能存入的就是null,所以还得继续比较
if(left==null||right==null) return false;
if(left.val!=right.val) return false;
//这里存放顺序很重要，方便下次取出比较。
q.add(left.left);
q.add(right.right);
q.add(left.right);
q.add(right.left);
}
return true;
}