LeetCode 101. Symmetric Tree 题解题目描述给你一个二叉树的根节点root检查它是否轴对称。示例 1输入root [1,2,2,3,4,4,3] 输出true示例 2输入root [1,2,2,null,3,null,3] 输出false解题思路方法一递归深度优先搜索思路一个二叉树是对称的当且仅当它的左子树和右子树是镜像对称的两个子树是镜像对称的条件是它们的根节点值相同左子树的左子树与右子树的右子树镜像对称左子树的右子树与右子树的左子树镜像对称使用递归的方式检查这三个条件复杂度分析时间复杂度O(n)其中 n 是二叉树中的节点个数。每个节点只被访问一次。空间复杂度O(h)其中 h 是二叉树的高度。递归调用的栈空间取决于二叉树的高度最坏情况下为 O(n)。方法二迭代广度优先搜索使用队列思路使用队列来实现广度优先搜索每次取出两个节点进行比较检查这两个节点的值是否相同然后将它们的子节点按照镜像对称的顺序加入队列如果队列中所有节点都满足镜像对称条件则二叉树是对称的复杂度分析时间复杂度O(n)其中 n 是二叉树中的节点个数。每个节点只被访问一次。空间复杂度O(n)最坏情况下队列的大小为 O(n)。代码实现方法一递归深度优先搜索# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True return self.isMirror(root.left, root.right) def isMirror(self, 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 (self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left))方法二迭代广度优先搜索# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right 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测试用例测试用例 1输入[1,2,2,3,4,4,3]输出true测试用例 2输入[1,2,2,null,3,null,3]输出false测试用例 3输入[]输出true测试用例 4输入[1]输出true总结本题是二叉树的经典问题主要考察对树的对称性的理解和遍历方法的应用。两种方法各有特点递归深度优先搜索代码简洁易懂逻辑清晰是最直观的解决方案。迭代广度优先搜索避免了递归的栈溢出问题适用于深度较大的树。在实际应用中递归方法通常是最首选的解决方案因为它代码简洁且易于理解。但在处理深度较大的树时迭代方法可能更为可靠。无论使用哪种方法核心思想都是相同的检查二叉树的左子树和右子树是否是镜像对称的。