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.
这道题一开始不知道如何下手，每次遇到这种需要比较结构的题，心里知道肯定是用递归比较简单，但自己没见过的题还是不知道该怎么开始，比如这里我到底要怎么去比较他们是不是对称，那岂不是要比较完每个节点的值以及左右子树？总之找不到一个很连贯的思路，或者说对递归函数的结构、写法太不熟练，导致形不成体系，没有通用的方法可以破题。
看了答案之后一是觉得自己怎么这么笨就没想到可以这样做，二是觉得这类题肯定是有通法的，比如这里的递归就是让你判断哪些情况肯定不是sysmmetric的，一一返回false, 剩下的肯定就是symmetric的了；
先是recursive的解法：
helper函数用来判断左右子树是否对称。如果两边都为空，是对称的（可以通过test case自己看到）。然后看几个不对称的情况：
- 一边为空，一边不为空，不对称；
- 两边的val不一样，不对称；
- 左边根节点的左子树与右边根节点的右子树不对称，不对称
- 左边根节点的右子树与右边根节点的左子树不对称，不对称
这里构造递归函数的时候最关键的就是后两种情况，能把它想清楚想明白这个recursion基本就能写出来了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null){
return true;
}
return helper(root.left, root.right);
}
private boolean helper(TreeNode l, TreeNode r){
if (l == null && r == null){
return true;
} else if (l == null || r == null){
return false;
}
if (l.val != r.val){
return false;
}
if (!helper(l.left, r.right)){
return false;
}
if (!helper(l.right, r.left)){
return false;
}
return true;
}
}
这道题还可以用迭代法做：用两个queue做BFS来遍历左右子树. 每一次poll()出来，用几个条件来判断是否对称：
- 一个为空，一个不为空，肯定不对称；
- 两个poll()出来的元素值不同，不对称；
注意之后每次offer进queue,左右两边的顺序要刚好相反，这样才能每次poll()出来的时候比较是否相等。 最后退出while循环后，还要判断是不是只有一个queue是empty,如果是那说明也是不对称的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null){
return true;
}
Queue<TreeNode> queueLeft = new LinkedList<>();
Queue<TreeNode> queueRight = new LinkedList<>();
queueLeft.offer(root);
queueRight.offer(root);
while (!queueLeft.isEmpty() && !queueRight.isEmpty()){
TreeNode nodeLeft = queueLeft.poll();
TreeNode nodeRight = queueRight.poll();
if (nodeLeft == null && nodeRight == null){
continue;
} else if (nodeLeft == null || nodeRight == null){
return false;
}
if (nodeLeft.val != nodeRight.val){
return false;
}
queueLeft.offer(nodeLeft.left);
queueLeft.offer(nodeLeft.right);
queueRight.offer(nodeRight.right);
queueRight.offer(nodeRight.left);
}
if (!queueLeft.isEmpty() || !queueRight.isEmpty()){
return false;
}
return true;
}
}
