### 题目

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.

### 老办法，分治递归

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
return (root == null)? true : areSymmetric(root.left,root.right);
}
public boolean areSymmetric(TreeNode one, TreeNode two) {
if (one == null || two == null) { return one == two; }
return (one.val == two.val) && areSymmetric(one.left,two.right) && areSymmetric(one.right,two.left);
}
}


### 迭代DFS遍历

    1
/ \
2   3
/   /
3   2


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) { return true; }
Deque<TreeNode> memo = new LinkedList<TreeNode>(); // 左半边节点历史
Deque<Boolean> directionMemo = new LinkedList<Boolean>(); // 左半边节点朝向历史
TreeNode cur = root;
boolean reachMid = false;
boolean fromLeft = false;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.offerFirst(cur);
if (fromLeft) { // note direction
direction.offerFirst(true);
} else {
direction.offerFirst(false);
}
cur = cur.left;
fromLeft = true;
}
cur = stack.pollFirst();
boolean isFromLeft = direction.pollFirst();
if (!reachMid) { // 没到达中点之前，积累memo
if (cur != root) {
memo.offerFirst(cur);
directionMemo.offerFirst(isFromLeft);
} else {
reachMid = true;
}
} else { // 过了中点以后，开始和memo里的内容比较
TreeNode sym = memo.pollFirst();
Boolean dirInMemo = directionMemo.pollFirst();
if (sym == null || sym.val != cur.val || dirInMemo == isFromLeft) { return false; }
}
cur = cur.right;
fromLeft = false;
}
return memo.isEmpty();
}
}


### 迭代BFS遍历

#### 代码

public boolean isSymmetric(TreeNode root) {
if (root == null) { return true; }
TreeNode cur = root;
stack.offerLast(root.left); stack.offerLast(root.right);
while (!stack.isEmpty()) {
TreeNode n1 = stack.pollFirst(), n2 = stack.pollFirst();
if (n1 == null && n2 == null) { continue; } // 一对null不算完，让stack吐干净
if ((n1 != null && n2 == null) || (n1 == null && n2 != null) || (n1.val != n2.val)) { return false; }
stack.offerLast(n1.left); stack.offerLast(n2.right);
stack.offerLast(n1.right); stack.offerLast(n2.left);
}
return true;
}