leetcode100:相同的树-输入：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：启发与优化