Leetcode 101. 对称二叉树

1.题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

2.思路分析

2.1 递归法

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

确定递归函数要处理的参数以及返回值

• 参数:left:TreeNode right:TreeNode
• 返回值:bool

确定终止条件

• 如果结点存在空结点或者节点值不相等

确定单层搜索逻辑

• 节点为空的情况:
  • left为空或者right为空 return False
  • left 和 right 均为空 return True
• 节点不为空的情况
  • left.val != right.val return False
  • left.val == right.val 递归处理左右节点

2.2 迭代法

当两个子树的根节点相等时，就比较:

左子树的 left 和 右子树的 right，这个比较是用递归实现的。

现在我们改用队列来实现，思路如下：

• 首先从队列中拿出两个节点(left 和 right)比较
• 将 left 的 left 节点和 right 的 right 节点放入队列
• 将 left 的 right 节点和 right 的 left 节点放入队列

3.代码实现

3.1 递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def compare(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            # 终止条件
            # 节点为空的情况
            if not (left or right):
                return True
            if not (left and right):
                return False
            # 节点不为空的情况
            # 节点不相等
            if left.val != right.val:
                return False
            return compare(left.left, right.right) and compare(left.right, right.left)

        if not root:
            return True
        return compare(root.left, root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 时间复杂度：O(n)
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(n)

3.2 迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root or not (root.left or root.right):
            return True
            # 用队列保存节点
        queue = [root.left, root.right]
        while queue:
            # 从队列中取出两个节点，再比较这两个节点
            left = queue.pop(0)
            right = queue.pop(0)
            # 如果两个节点都为空就继续循环，两者有一个为空就返回false
            if not (left or right):
                continue
            if not (left and right):
                return False
            if left.val != right.val:
                return False
            # 将左节点的左孩子， 右节点的右孩子放入队列
            queue.append(left.left)
            queue.append(right.right)
            # 将左节点的右孩子，右节点的左孩子放入队列
            queue.append(left.right)
            queue.append(right.left)
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 时间复杂度：O(n)
• 空间复杂度：O(n)