leetcode100:相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

步骤1：问题定义与分析

问题性质

该问题是典型的二叉树递归判断问题，要求检验两棵二叉树是否在结构和节点值上完全相同。

输入输出条件

1. 输入：
   • 两棵二叉树的根节点 p 和 q，它们可能为空，也可能有多达 100 个节点。
   • 每个节点的值范围在 [-10^4, 10^4]。
2. 输出：
   • 如果两棵二叉树完全相同，返回 true；否则返回 false。

限制与边界条件

1. 边界条件：
   • p 和 q 同时为空，返回 true。
   • 只有一棵树为空，返回 false。
2. 复杂度限制：
   • 树的节点数最多为 100，因此即使采用递归方法，算法的时间复杂度应该控制在 O(n)，空间复杂度（递归栈深度）在 O(h)，其中 n 为树的节点数，h 为树的高度。

步骤2：解题思路分析与算法设计

解题分解步骤

1. 递归判断两棵树的根节点：
   • 如果根节点的值不相等，则两棵树不相同。
   • 如果根节点的值相等，则递归比较左子树和右子树是否相同。
2. 终止条件：
   • 两棵树的当前节点都为空时，返回 true（子树相同）。
   • 只有一棵树的当前节点为空时，返回 false（子树不同）。
3. 递归子问题：
   • 对于两棵树 p 和 q，分别递归调用其左子树 p.left 和 q.left 以及右子树 p.right 和 q.right，并在递归过程中判断子树是否相同。

递归设计思路

采用深度优先搜索（DFS）进行递归判断，每次判断当前节点及其子节点是否一致。算法的逻辑简单且直观：

1. 当前节点为空时返回结果；
2. 判断当前节点值是否一致；
3. 递归比较左子树和右子树。

算法复杂度

• 时间复杂度：O(n)，其中 n 为两棵树中节点数的最小值，每个节点访问一次。
• 空间复杂度：O(h)，其中 h 为递归调用栈的深度，最坏情况下（链式结构）为 O(n)，平均情况下为 O(log n)。

步骤3：C++代码实现

步骤4：启发与优化

1. 算法的优化性：

   • 使用递归直接检查左右子树，保证算法清晰简洁。
   • 如果提前发现不相同的节点，立即终止递归，提升效率。

2. 处理大规模数据的能力：

   • 通过改用非递归的栈或队列实现（如广度优先搜索 BFS），可以在避免递归栈溢出的同时保持时间复杂度不变。

步骤5：实际应用场景

场景：文件夹结构比较

在文件系统中，文件夹可以用树结构表示，每个节点是文件或子文件夹。此算法可以用于比较两个文件夹是否完全相同：

• 节点值表示文件名或文件大小。
• 结构相同表示两个文件夹具有相同的目录层次。

实现示例

1. 提取两个文件夹的树结构。
2. 调用 isSameTree 函数判断结构和内容是否一致。
3. 如果不一致，标记差异的节点。

这种方法在备份验证、文件同步系统中非常实用。