Symmetric Tree

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.

递归：

判断左右两颗子树是否对称，只要两颗子树的根节点值相同，并且左边子树的左子树和右边子树饿右子树对称 且 左边子树的右子树和右边子树的左子树对称

一开始先检查 input，如果 null 也是 symmetric，然后我们进入 recursive help function。

先看两个 node 是不是都是 null，如果都是 null 那么也是对称的。如果只有其中一个是 null 那么很明显这个数就是不对称的。

如果两个都不是 null 并且值相等，那么我们就 recursive 继续往下走。

复杂度分析：时间 O(n) 空间 O(1)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True        
        return self.help(root.left, root.right)

    def help(self, p, q):
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.help(p.left,q.right) and self.help(p.right, q.left)
        return False

DFS

用两个栈，左栈保存根节点的左孩子，右栈保存根节点的右孩子，每次从两个栈中取出一个值，然后比较，如果相同则把从左栈中取出的节点的左孩子和右孩子放进左栈；相对的，把右栈中取出的节点的右孩子和左孩子放进右栈。要注意的是左栈取出的节点放孩子的顺序是先左后右，右栈则是先右后左。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        stackLeft, stackRight = [root.left], [root.right]
        while stackRight and stackRight:
            leftNode = stackLeft.pop()
            rightNode = stackRight.pop()
            if not leftNode and not rightNode:
                continue
            if leftNode and rightNode and leftNode.val == rightNode.val:
                stackLeft.append(leftNode.left)
                stackLeft.append(leftNode.right)
                stackRight.append(rightNode.right)
                stackRight.append(rightNode.left)
            else:
                return False
        return True