题目

原题地址

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

思路

对称问题不能直接递归解决，要一层一层考虑，最左边的节点要跟最右边的节点比较，从左边数第二的节点要跟从右边数第二的节点比较......所以就用两个列表来保存节点，从根节点开始，一个由左向右储存左子树的节点，一个由右向左储存右子树的节点。这样保证了两个列表pop出来的最后一个节点是同一层中位置对称的两个节点，然后就可以逐个比较是否相同。

python代码

# 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
        """
        def isSame(node1, node2):
        # 比较两个节点是否相同
            if node1 == None and node2 == None:
                return True
            elif node1 != None and node2 != None and node1.val == node2.val:
                return True
            else:
                return False
        
            
        if root == None:
            return True
        left_list = []
        right_list = []
        left_list.append(root.left)
        right_list.append(root.right)
        while(len(left_list) > 0):
            # 逐个比较两个对应位置的节点是否相同
            left = left_list.pop()
            right = right_list.pop()
            if not isSame(left, right):
                return False
            
            if left != None:
                # 由左向右储存左子树中的节点
                left_list.append(left.left)
                left_list.append(left.right)

                # 由右向左储存右子树中的节点
                right_list.append(right.right)
                right_list.append(right.left)
        return True