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.
題意：判斷一個二叉樹是不是一個鏡面樹恩够，想象把二叉樹反轉(zhuǎn)判哥，得到的樹是不是和原樹相同忱叭。
思路：
一個二叉樹如果是鏡面樹需要滿足兩個條件：1、根節(jié)點的左右葉子節(jié)點值相同轿曙；2弄捕、左節(jié)點的左子樹是右節(jié)點的右子樹的鏡面僻孝，左節(jié)點的右子樹是右節(jié)點的左子樹的鏡面。
編碼時守谓，首先需要對輸入的參數(shù)做校驗穿铆，即處理參數(shù)是null的幾種情況；然后比較左右節(jié)點值是否相同斋荞；如果符合條件繼續(xù)遞歸判斷各自的左右子樹是否滿足條件荞雏。
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);
}
下面是非遞歸版本，思路是一樣的平酿，需要用一個隊列來存儲每次要比較的一對鏡像節(jié)點凤优。
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;
}