题目描述

[EN | CN]

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

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

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

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

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

进阶:

你可以运用递归和迭代两种方法解决这个问题吗?

解法 1:递归

对于一棵树是否为镜像对称,我们可以转化为判断左右两棵子树是否为镜像对称,从而将问题分解为更小规模的问题,并可以据此进行递归。

假设树的结点树一共为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历整棵树;
  • 空间复杂度为 $O(n)$,递归层数与树高度有关。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# 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:
        def check(root1, root2):
            if not root1 and not root2:
                return True
            if not root1 or not root2:
                return False
            return (root1.val == root2.val and 
                    check(root1.left, root2.right) and 
                    check(root1.right, root2.left))

        if not root:
            return True
        return check(root.left, root.right)
  • 执行用时:40 ms,在所有 Python3 提交中击败了 88.91% 的用户。
  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 6.06% 的用户。

解法 2:迭代

迭代跟递归差不多,无非是多用一个队列来保存即将对比的树,复杂度也相同。

实现与结果略。