描述
给定二叉树，返回它是否是自身的镜像（即这棵二叉树是否对称）。

在线评测地址：领扣题库官网

样例1
输入: {1,2,2,3,4,4,3}
输出: true
解释:
    1
   / \
  2   2
 / \ / \
3  4 4  3
{1,2,2,3,4,4,3}这棵二叉树是对称的

样例2
输入: {1,2,2,#,3,#,3}
输出: false
解释:
    1
   / \
  2   2
   \   \
   3    3
很显然这棵二叉树并不对称

用递归和迭代的方法来解决这个问题(2种解法)
代码
使用分治法 Divide Conquer 的版本

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    def isSymmetric(self, root):
        if not root:
            return True
        return self._is_symmetric(root.left, root.right)
        
    def _is_symmetric(self, left_root, right_root):
        if left_root is None and right_root is None:
            return True
        if left_root is None or right_root is None:
            return False
        if left_root.val != right_root.val:
            return False
            
        left = self._is_symmetric(left_root.left, right_root.right)
        right = self._is_symmetric(left_root.right, right_root.left)
        return left and right

使用Iteration的版本

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    
    def isSymmetric(self, root):
        inorder = self.inorder(root, reverse=False)
        reverse_inorder = self.inorder(root, reverse=True)
        if inorder != reverse_inorder:
            return False
            
        preorder = self.preorder(root, reverse=False)
        reverse_preorder = self.preorder(root, reverse=True)
        return preorder == reverse_preorder
        
    def get_left(self, node, reverse):
        if reverse:
            return node.right
        return node.left
        
    def get_right(self, node, reverse):
        if reverse:
            return node.left
        return node.right
        
    def preorder(self, root, reverse):
        stack = [root]
        order = []
        while stack:
            node = stack.pop()
            order.append(node.val)
            right = self.get_right(node, reverse)
            if right:
                stack.append(right)
            left = self.get_left(node, reverse)
            if left:
                stack.append(left)
        return order
        
    def inorder(self, root, reverse):
        stack = []
        while root is not None:
            stack.append(root)
            root = self.get_left(root, reverse)
            
        order = []
        while stack:
            node = stack[-1]
            order.append(node.val)
            right = self.get_right(node, reverse)
            if right is not None:
                node = right
                while node is not None:
                    stack.append(node)
                    node = self.get_left(node, reverse)
            else:
                stack.pop()
                while stack and self.get_right(stack[-1], reverse) == node:
                    node = stack.pop()
        
        return order

使用 BFS 算法的版本

Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

class Solution:

    @param root: root of the given tree
    @return: whether it is a mirror of itself 
    """
    def isSymmetric(self, root):
        queue = [root]
        while queue:
            next_queue = []
            for i in range(len(queue)):
                if queue[i] is None:
                    continue
                next_queue.append(queue[i].left)
                next_queue.append(queue[i].right)
            if not self.is_mirror(next_queue):
                return False
            queue = next_queue
        return True
        
    def is_mirror(self, queue):
        left, right = 0, len(queue) - 1
        while left < right:
            if not self.is_same(queue[left], queue[right]):
                return False
            left, right = left + 1, right - 1
        return True
        
    def is_same(self, node1, node2):
        if node1 and node2:
            return node1.val == node2.val
        return node1 is None and node2 is None

更多题解参考：九章官网solution