文章目录

• 100.相同的树
• • 题目
  • 题解

100.相同的树

题目

给你两棵二叉树的根节点 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题容易想到的是使用两个指针分别指向两棵树的相同位置，对比该位置的节点值是否相同，如果不同可以直接返回false，如果相同在继续比较下一个节点。

既然要比较所有的节点是否相同，那么考点：遍历二叉树。

遍历二叉树一共有4种办法，前序遍历、中序遍历、后序遍历和层序遍历。那么我们选择哪一种遍历方法？

我觉得都可以，我选择前序遍历。从上至下的开始比较，如果不同就直接返回。

递归三部曲

1. 递归的参数和递归的返回值
   递归的参数是指向两个树相同的位置指针p，q，返回值是以p和q为根节点的两棵树是否是相同的。

递归的作用可以抽象为：以p和q为根节点的两棵树是否是相同的。

var isSameTree = function(p, q) {} //返回布尔值

2. 递归的终止条件
   当p和q都为空时就不用比较了，递归可以终止了。

if(q==null && p==null)return true;

3. 本层递归的逻辑

递归的作用可以抽象为：以p和q为根节点的两棵树是否是相同的。
本层递归的作用就是比较p和q指向的节点是否相同，这里有三种情况

• p为空，q不为空 以p和q为根节点的两棵树肯定不同
• q为空，p不为空 以p和q为根节点的两棵树肯定不同
• p、q都不为空，就需要比较两个节点值是否相同
  • 如果不同，那肯定不是相同的树
  • 如果相同，那么就需要看以p.left和q.left为根的子树是否相同，以p.right和q.left为根的子树是否相同

//前序遍历
if(q==null) return false;
if(p==null) return false;
if(p.val != q.val)return false; //处理当前节点
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//左 和 右

代码

var isSameTree = function(p, q){
if(q==null && p==null)return true;
if(q==null) return false;
if(p==null) return false;
if(p.val != q.val)return false; //处理当前节点
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//左 和 右
}

可以练习101.对称二叉树