100、相同的树
100、相同的树
题意
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
难度
简单
示例
示例 1：
100.%E7%9B%B8%E5%90%8C%E7%9A%84%E6%A0%91-20231116085854.png
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
100.%E7%9B%B8%E5%90%8C%E7%9A%84%E6%A0%91-20231116085943.png
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
100.%E7%9B%B8%E5%90%8C%E7%9A%84%E6%A0%91-20231116090002.png
输入：p = [1,2,1], q = [1,1,2]
输出：false
分析
本题我们还是使用解决二叉树问题中最常用的办法——“递归”。
假设我们现在获得了两棵树的根节点（p 和 q），一眼看出他俩是相同的很难，但也有例
外，比如说两个都是 null，空树自然是一样的。
再换另外一个角度，想要一眼看出两棵树是不同的，只要 p.val != q.val，我们就能分辨
出。
至于其他的情况，就不能这么简单地分辨了，因为涉及到左子树和右子树相同的情况，但
是不要忘记——递归！
只要继续递归处理各自的左子树和右子树，问题就迎刃而解了，换句话说，p 的左子树必
然和 q 的左子树是相同的，p 的右子树必然和 q 的右子树也是相同的，而左子树和右子树
同样也是二叉树。
这时候整个算法的大概框架就浮现出来了——以递归为基础，先判断我们前面提到的两种
最直观的情况，否则就递归判断左子树和右子树！
好，来看整个题解，看一眼注释基本就明白了，非常简单。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
*}
*/
class Solution {
// 方法用于比较两个二叉树 p 和 q 是否完全相同
public boolean isSameTree(TreeNode p, TreeNode q) {
// 如果两个树都是空的，则它们相同
if (p == null && q == null) {
return true;
}
// 如果一个树为空而另一个不为空，则它们不相同
if (p == null || q == null) {
return false;
}
// 检查当前节点的值是否相等，并递归地检查左右子树
// 只有当前节点值相等且对应的左子树和右子树也都相等时，才认为整个树相等
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right,
q.right);
}
}
因为最多只可能遍历整个树的所有节点一次，所以时间复杂度为$ O(n) $，非常优秀。
100.%E7%9B%B8%E5%90%8C%E7%9A%84%E6%A0%91-20231116091302.png
好，对于输入 p = [1,2] 和 q = [1,null,2]，我们来模拟一下整个题解过程：
树 p 的结构：
1
/
2
树 q 的结构：
1
2
按照题解的方法，我们逐步比较这两棵树是否相同：
1. 初始调用 **isSameTree**：
– 首先比较根节点 p（值为 1）和根节点 q（值为 1）。它们的值相等，所以我
们继续。
2. 递归比较左子树：
– 接下来，我们比较 p 的左子树（值为 2）和 q 的左子树（null）。
– 因为 p 的左子树是非空的，而 q 的左子树是空的，所以这里它们不相同。
– 此时，方法返回 false。
3. 递归比较右子树：
– 这一步在本例中不会执行，因为一旦左子树的比较返回了 false，整个方法就
会立即返回 false。
所以，根据题解的逻辑，这两棵树不是相同的树，最终结果为 false。这是因为尽管它们
的根节点相同，但它们的左子树不同（一个是非空，另一个是空）。树的结构和节点值都
需要完全匹配，才能认为两棵树是相同的。
总结
简单的代码，简单的思路，背后蕴藏着的其实是我们不断锤炼的解题能力，100 题了，继
续加油吧。
力扣链接：https://leetcode.cn/problems/same-tree/