Open sl1673495 opened 4 years ago
DFS
var isSameTree = function (p, q) {
let flag = true;
const dfs = (p, q) => {
//节点都不在,return
if (!p && !q) return;
//节点都在,进行比较是否相等
if (p && q) {
if (p.val !== q.val) return flag = false;
//节点相等,继续下一层比较
dfs(p.left, q.left);
dfs(p.right, q.right);
} else {
//节点一个在,一个不在,直接返回false
return flag = false;
}
}
dfs(p, q);
return flag;
};
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/same-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
DFS
深度优先遍历就是直接递归比较,把 left 和 right 节点也视为一棵树。继续调用
isSameTree
方法。题解
BFS
BFS 也是标准的思路,就是把节点放进一个队列里,然后在处理节点的时候遇到有 left 或 right 子节点,就继续放进队列里,下一轮循环继续处理。