Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/
2 2
/ \ /
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/
2 2
\
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
题意：判断一个二叉树是不是一个镜面树，想象把二叉树反转，得到的树是不是和原树相同。
思路：
一个二叉树如果是镜面树需要满足两个条件：1、根节点的左右叶子节点值相同；2、左节点的左子树是右节点的右子树的镜面，左节点的右子树是右节点的左子树的镜面。
编码时，首先需要对输入的参数做校验，即处理参数是null的几种情况；然后比较左右节点值是否相同；如果符合条件继续递归判断各自的左右子树是否满足条件。
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return helper(left.left, right.right) && helper(left.right, right.left);
}
下面是非递归版本，思路是一样的，需要用一个队列来存储每次要比较的一对镜像节点。
public boolean isSymmetric1(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}