【剑指Offer刷题系列】判断对称二叉树
目录
- 问题描述
- 示例
- 示例 1：
- 示例 2：
- 提示
- 思路解析
- 核心思路：
- 选择方法：
- 代码实现
- Python 实现
- 方法二：迭代（使用队列）
- 测试代码
- 复杂度分析
- 时间复杂度
- 空间复杂度
问题描述
请设计一个函数判断一棵二叉树是否 轴对称。
一棵二叉树是 对称 的，如果它与其自身的镜像是相同的。
示例
示例 1：
输入：
root = [6,7,7,8,9,9,8]
输出：
true
解释：
从图中可看出树是轴对称的。
示例 2：
输入：
root = [1,2,2,null,3,null,3]
输出：
false
解释：
从图中可看出最后一层的节点不对称。
提示
0 <= 节点个数 <= 1000
原题链接： https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/description/ 及 https://leetcode-cn.com/problems/symmetric-tree/ 。
思路解析
本题要求判断一棵二叉树是否 轴对称。一棵二叉树是 对称 的，如果它与其自身的镜像相同。
核心思路：
-
递归方法：
- 比较树的左子树和右子树是否互为镜像。
- 对于每一对对应节点，检查它们的值是否相同，并递归检查它们的子节点是否互为镜像。
- 具体来说，左子树的左子节点与右子树的右子节点应相等，左子树的右子节点与右子树的左子节点应相等。
-
迭代方法：
- 使用队列进行广度优先搜索。
- 将左子树和右子树的对应节点成对入队。
- 每次从队列中取出一对节点，比较它们的值是否相同，并将它们的子节点按照镜像顺序入队。
选择方法：
- 递归方法实现简单，代码简洁。
- 迭代方法避免了递归的调用栈，适用于树的高度较大时。
本题节点数目上限为 1000，递归深度不会过大，因此推荐使用递归方法。
代码实现
Python 实现
# Definition for a binary tree node.
from typing import Optional
from collections import deque
class TreeNode:
def __init__(self, val=0, left: Optional['TreeNode']=None, right: Optional['TreeNode']=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def is_mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
if not left and not right:
return True
if not left or not right:
return False
if left.val != right.val:
return False
# 递归检查左左和右右，左右和右左
return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
return is_mirror(root.left, root.right)
方法二：迭代（使用队列）
from collections import deque
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
queue = deque([(root.left, root.right)])
while queue:
left, right = queue.popleft()
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False
# 将对应的子节点成对入队
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True
测试代码
import unittest
class TestIsSymmetric(unittest.TestCase):
def build_tree(self, values):
"""
根据层序遍历的数组构建二叉树。
None 表示该位置没有节点。
"""
if not values:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
while queue and i < len(values):
current = queue.popleft()
if current:
# 左子节点
if i < len(values) and values[i] is not None:
current.left = TreeNode(values[i])
queue.append(current.left)
i += 1
# 右子节点
if i < len(values) and values[i] is not None:
current.right = TreeNode(values[i])
queue.append(current.right)
i += 1
return root
def test_example1(self):
root_vals = [6,7,7,8,9,9,8]
root = self.build_tree(root_vals)
solution = Solution()
self.assertTrue(solution.isSymmetric(root), "示例1失败")
def test_example2(self):
root_vals = [1,2,2,None,3,None,3]
root = self.build_tree(root_vals)
solution = Solution()
self.assertFalse(solution.isSymmetric(root), "示例2失败")
def test_empty_tree(self):
root_vals = []
root = self.build_tree(root_vals)
solution = Solution()
self.assertTrue(solution.isSymmetric(root), "空树测试失败")
def test_single_node(self):
root_vals = [1]
root = self.build_tree(root_vals)
solution = Solution()
self.assertTrue(solution.isSymmetric(root), "单节点测试失败")
def test_two_nodes_symmetric(self):
root_vals = [1,2,2]
root = self.build_tree(root_vals)
solution = Solution()
self.assertTrue(solution.isSymmetric(root), "对称的两节点测试失败")
def test_two_nodes_asymmetric(self):
root_vals = [1,2,3]
root = self.build_tree(root_vals)
solution = Solution()
self.assertFalse(solution.isSymmetric(root), "不对称的两节点测试失败")
def test_balanced_tree(self):
root_vals = [1,2,2,3,4,4,3]
root = self.build_tree(root_vals)
solution = Solution()
self.assertTrue(solution.isSymmetric(root), "平衡树测试失败")
def test_unbalanced_tree(self):
root_vals = [1,2,2,None,3,None,3]
root = self.build_tree(root_vals)
solution = Solution()
self.assertFalse(solution.isSymmetric(root), "不平衡树测试失败")
if __name__ == "__main__":
unittest.main(argv=[''], exit=False)
输出：
........
----------------------------------------------------------------------
Ran 8 tests in 0.XXXs
OK
复杂度分析
时间复杂度
-
递归方法：
- 总体复杂度：O(n)，其中
n是二叉树的节点数。 - 详细分析：
- 每个节点仅被访问一次。
- 在访问每个节点时，进行常数时间的操作（比较值和递归调用）。
- 总体复杂度：O(n)，其中
-
迭代方法：
- 总体复杂度：O(n)，其中
n是二叉树的节点数。 - 详细分析：
- 每个节点仅被访问一次。
- 队列的入队和出队操作均为常数时间。
- 总体复杂度：O(n)，其中
空间复杂度
-
递归方法：
- 总体复杂度：O(h)，其中
h是二叉树的高度。 - 详细分析：
- 递归调用栈的空间复杂度与树的高度成正比。
- 在最坏情况下（如完全不平衡的树），空间复杂度为 O(n)。
- 在最优情况下（如完全平衡的树），空间复杂度为 O(log n)。
- 总体复杂度：O(h)，其中
-
迭代方法：
- 总体复杂度：O(w)，其中
w是二叉树的最大宽度。 - 详细分析：
- 队列中同时存储的节点数不超过当前层的节点数。
- 在最坏情况下（如完全二叉树的底层），空间复杂度为 O(n/2) = O(n)。
- 总体复杂度：O(w)，其中
通过上述方法，我们可以高效地判断一棵二叉树是否为对称二叉树。递归方法实现简单直观，适用于大多数场景；迭代方法则通过使用队列避免了递归带来的潜在栈溢出问题，特别适用于节点数量较大或树高度较高的情况。