Sui Xin's Blog

[LeetCode]101. 对称二叉树（Symmetric Tree）

Posted on In Disqus:

题目描述

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

例如，二叉树 [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. 解法一：递归。
  2. 解法二：迭代。使用队列将应该比较的节点加入到队列中，依次出队比较然后再添加子节点。

代码

Python 3.6

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        return self.is_symmetric_core(root.left, root.right)
    
    def is_symmetric_core(self, left, right):
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        return left.val == right.val and self.is_symmetric_core(left.left, right.right) and self.is_symmetric_core(left.right, right.left)

执行用时 : 80 ms
内存消耗 : 14 MB

解法二：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        queue = [(root.left, root.right)]
        while queue:
            node1, node2 = queue.pop(0)
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            queue.append((node1.left, node2.right))
            queue.append((node1.right, node2.left))
        return True

执行用时 : 72 ms
内存消耗 : 13.8 MB

Related Posts