​

1. 题目描述

2.  题目分析与解析

要编写一个判断两棵二叉树是否完全相同的代码，首先需要理解何谓“完全相同”的二叉树。完全相同意味着两棵树的结构完全一致，并且所有对应的节点上的值也必须相同。

1. 定义问题

首先明确问题定义：给定两棵二叉树的根节点，判断这两棵树是否完全相同。

2. 基础情况考虑

对于递归函数，你需要首先考虑最简单的情况，也就是递归的终止条件：

• 两个节点都为空：如果两个树的当前节点都是空，那么在这一部分，它们显然是相同的，应返回true。

• 一个节点为空：如果其中一个节点为空而另一个不为空，这两棵树在此处结构不同，应返回false。

3. 分解问题

一旦通过了基础情况的判断，下一步是比较当前两个节点的值：

• 节点值不相同：如果两个节点的值不一样，那么这两棵树在这个节点上不相同，应返回false。

4. 递归比较子树

如果当前节点的值相同，接下来需要判断这两个节点的子树是否相同：

• 使用递归分别比较左子树和右子树。只有当一个节点的左子树与另一个节点的左子树相同，且右子树也相同，这两个节点才真正相同。

5. 合并结果

根据递归调用的结果，如果左右子树都相同，则返回true，否则返回false。

代码思路：

1. 检查两个节点是否同时为空。

2. 检查两个节点是否有一个为空而另一个不为空。

3. 比较两个节点的值。

4. 递归地比较两个节点的左子树和右子树。

这个逻辑清晰而直接，使用递归使得代码简洁且易于理解。这种方法也体现了分而治之的策略，将大问题（比较整棵树）分解成小问题（比较节点和其子节点）。通过递归调用，小问题的解决方案帮助我们解决整个大问题。

3. 代码实现

4. 相关复杂度分析

要分析给定代码的时间和空间复杂度，我们先要考虑每个函数调用涉及的操作以及如何扩展到整个树。

时间复杂度

1. 遍历所有节点：这段代码通过递归调用函数isSameTree来访问两棵树的每个节点。在最坏的情况下，即当两棵树完全相同或者只在最后一个节点处不同，我们需要遍历树中的所有节点。因此，时间复杂度依赖于树中节点的数量。

2. 每个节点访问一次：对于每个节点，我们执行常数时间的操作，包括比较节点的值，以及检查节点是否为null。因此，每个节点的处理时间是常数，O(1)。

综上，如果树有n个节点，那么时间复杂度是O(n)，因为需要访问每个节点一次。

空间复杂度

空间复杂度主要由递归调用栈的深度决定，这取决于树的结构：

1. 最坏情况 - 不平衡树：如果树是高度不平衡的，例如所有节点都只有左子节点或右子节点，那么递归调用将会跟随一条从根到叶的路径，递归深度等于较矮的那个树的高度，因为在对比时发现不等就会立刻返回。在这种情况下，如果树的高度是h，那么空间复杂度将是远小于O(h)的。

2. 最好情况 - 完全平衡树：对于完全平衡的二叉树，高度大约是log(n)，其中n是节点数。因此，递归调用的深度也是log(n)，空间复杂度将是O(log(n))。

3. 平均情况：对于大多数实际应用中的树结构（既非完全不平衡，也非完全平衡），空间复杂度一般视为O(log(n))，假设树大致平衡。

综合来看，时间复杂度是O(n)，空间复杂度在O(log(n))。