### 判断两个二叉树是否相等的实现方法 在Python中，判断两个二叉树是否相等可以通过递归或迭代的方式实现。以下是具体的实现方法和代码示例。 #### 方法 1：递归实现 递归方法的核心思想是比较两个节点的值是否相等，并递归地比较其左右子树。如果两棵树的所有对应节点都相等，则认为这两棵树相等。 ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: # 如果两个节点都为空，则返回True if not p and not q: return True # 如果其中一个节点为空，另一个不为空，则返回False if not p or not q: return False # 如果当前节点值不相等，则返回False if p.val != q.val: return False # 递归比较左子树和右子树 return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) ``` 此方法的时间复杂度为 \(O(n)\)，其中 \(n\) 是节点的数量[^3]。空间复杂度取决于递归栈的深度，在最坏情况下为 \(O(n)\)[^4]。 #### 方法 2：迭代实现 迭代方法使用队列（或栈）来逐层比较两棵树的节点。每次从队列中取出一对节点进行比较，若相等则将其左右子节点加入队列继续比较。 ```python from collections import deque class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: # 使用双端队列存储节点对 queue = deque([(p, q)]) while queue: node1, node2 = queue.popleft() # 如果两个节点都为空，跳过 if not node1 and not node2: continue # 如果其中一个节点为空，另一个不为空，返回False if not node1 or not node2: return False # 如果节点值不相等，返回False if node1.val != node2.val: return False # 将左右子节点加入队列 queue.append((node1.left, node2.left)) queue.append((node1.right, node2.right)) return True ``` 此方法同样具有 \(O(n)\) 的时间复杂度和 \(O(n)\) 的空间复杂度[^4]。 ### 注意事项 - 在递归方法中，必须确保在递归调用之前已经处理了所有可能的边界条件。 - 在迭代方法中，队列的使用可以避免递归带来的栈溢出问题，适合处理深度较大的树。