LeetCode中如何解决相同的树问题

# LeetCode中如何解决相同的树问题

## 引言

在LeetCode的算法题库中，"相同的树"（Same Tree）是一个经典的二叉树相关问题，通常被标记为简单难度。该问题要求判断两棵二叉树在结构和节点值上是否完全相同。本文将深入探讨该问题的多种解法，包括递归法、迭代法，并分析其时间复杂度和空间复杂度，最后提供相应的代码实现。

---

## 问题描述

**题目编号**：100  
**题目名称**：相同的树  
**题目描述**：给定两棵二叉树的根节点 `p` 和 `q`，编写一个函数来检验它们是否相同。如果两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**示例 1**：

输入: p = [1,2,3], q = [1,2,3] 输出: true

**示例 2**：

输入: p = [1,2], q = [1,null,2] 输出: false

---

## 解题思路

### 方法一：递归法

递归是解决树问题的常见方法。对于两棵树是否相同，可以通过以下步骤判断：

1. **终止条件**：
   - 如果两棵树的当前节点均为 `null`，返回 `true`。
   - 如果一棵树的当前节点为 `null` 而另一棵不为 `null`，返回 `false`。
   - 如果两棵树的当前节点值不同，返回 `false`。

2. **递归逻辑**：
   - 分别递归比较左子树和右子树。

#### 代码实现（Python）
```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:
        if not p and not q:
            return True
        if not p or not q:
            return 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 是树的节点数。每个节点访问一次。
• 空间复杂度：O(h)，h 是树的高度。递归栈的深度取决于树的高度。

方法二：迭代法（广度优先搜索）

递归法可能存在栈溢出风险（尤其是树很深时），因此可以使用迭代法。通过队列（或栈）实现广度优先搜索（BFS），逐层比较节点。

算法步骤

1. 初始化队列，将两棵树的根节点入队。
2. 每次从队列中取出两个节点比较：
   • 如果节点值不同，返回 false。
   • 如果左子树或右子树结构不一致，返回 false。
3. 将子节点按顺序入队。

代码实现（Python）

from collections import deque

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        queue = deque([(p, q)])
        while queue:
            node_p, node_q = queue.popleft()
            if not node_p and not node_q:
                continue
            if not node_p or not node_q:
                return False
            if node_p.val != node_q.val:
                return False
            queue.append((node_p.left, node_q.left))
            queue.append((node_p.right, node_q.right))
        return True

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，最坏情况下队列存储所有叶子节点。

方法三：迭代法（深度优先搜索）

类似BFS，但使用栈实现深度优先搜索（DFS）。

代码实现（Python）

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        while stack:
            node_p, node_q = stack.pop()
            if not node_p and not node_q:
                continue
            if not node_p or not node_q:
                return False
            if node_p.val != node_q.val:
                return False
            stack.append((node_p.left, node_q.left))
            stack.append((node_p.right, node_q.right))
        return True

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(h)，h 为树的高度。

边界条件与注意事项

1. 空树处理：两棵树均为空时返回 true。
2. 节点值类型：题目中节点值通常是整数，但实际应用中需考虑其他类型。
3. 树的结构差异：即使部分子树相同，整体结构不同仍需返回 false。

扩展思考

变种问题

1. 对称树：LeetCode 101题（Symmetric Tree）是相同树的变种，要求树镜像对称。
2. 子树匹配：LeetCode 572题（Subtree of Another Tree）判断一棵树是否是另一棵树的子树。

优化方向

• 并行遍历：对于大规模树，可探索并行化递归或迭代。
• 短路优化：在迭代中提前终止不必要的比较。

总结

解决“相同的树”问题主要有递归和迭代两种思路： - 递归法：代码简洁，适合树深度不大的场景。 - 迭代法：通过队列或栈实现，避免递归栈溢出风险。

根据实际场景选择合适的方法，并注意边界条件处理。

附录：完整测试用例

# 测试用例1：两棵树相同
p = TreeNode(1, TreeNode(2), TreeNode(3))
q = TreeNode(1, TreeNode(2), TreeNode(3))
assert Solution().isSameTree(p, q) == True

# 测试用例2：结构不同
p = TreeNode(1, TreeNode(2))
q = TreeNode(1, None, TreeNode(2))
assert Solution().isSameTree(p, q) == False

”`