对称二叉树

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

示例代码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

        def dfs(left, right):
            if (not left) and (not right):
                return True
            if (not left) or (not right):
                return False
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
            
        return dfs(root.left, root.right)

示例代码2：

# 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
        if (not root.left) and (not root.right):
            return True
        if (not root.left) or (not root.right):
            return False
        # 用队列保存节点
        queue = [root.left, root.right]

        while queue:
            # 从队列中取出两个节点，再比较这两个节点
            node1 = queue.pop(0)
            node2 = queue.pop(0)

            # 如果两个节点都为空就继续循环，两者有一个为空就返回false
            if (not node1) and (not node2):
                continue
            if (not node1) or (not node2):
                return False
            if node1.val != node2.val:
                return False
            
            # 将左节点的左孩子， 右节点的右孩子放入队列
            queue.append(node1.left)
            queue.append(node2.right)
            # 将左节点的右孩子，右节点的左孩子放入队列
            queue.append(node1.right)
            queue.append(node2.left)
        return True