91 lines
2.6 KiB
JavaScript
91 lines
2.6 KiB
JavaScript
/**
|
||
* Definition for a binary tree node.
|
||
* function TreeNode(val) {
|
||
* this.val = val;
|
||
* this.left = this.right = null;
|
||
* }
|
||
*/
|
||
/**
|
||
* @param {TreeNode} root
|
||
* @param {TreeNode} p
|
||
* @param {TreeNode} q
|
||
* @return {TreeNode}
|
||
* https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-interview-150
|
||
*/
|
||
const lowestCommonAncestor = function (root, p, q) {
|
||
|
||
};
|
||
|
||
/*
|
||
利用dfs来遍历每一节点，根据定义，如果节点x是p和q的最近的公共祖先无外乎就下面几种情况
|
||
1. p在x的左子树，q在x的右子树，反之一样 lson && rson
|
||
2. p就是x，那么q一定存在 lson 或 rson, (x===p||x===q) && (lson || rson)
|
||
在遍历的时候只要满足上面条件的节点就是要寻找的最近公共祖先
|
||
*/
|
||
function f1(root, p, q) {
|
||
let ans;
|
||
/*
|
||
dfs遍历只干一件事，就是判断root表示的这个数是否有p或者q
|
||
*/
|
||
const dfs = (root, p, q) => {
|
||
// 如果当前节点为空返回false
|
||
if (!root) return false;
|
||
|
||
// 查找左右子树是否包含q或q
|
||
const lson = dfs(root.left, p, q);
|
||
const rson = dfs(root.right, p, q);
|
||
|
||
// 判断当前节点是否是最近公共祖先
|
||
if ((lson && rson) || ((root === p || root === q) && (lson || rson))) {
|
||
ans = root;
|
||
}
|
||
|
||
// 返回函数判断
|
||
return lson || rson || root === p || root === q;
|
||
};
|
||
dfs(root, p, q);
|
||
return ans;
|
||
}
|
||
|
||
/*
|
||
遍历所有的节点，给他们设置对应的父节点，之后不停的回溯q的父节点，并且把它们存入到一个set中，之后再回溯p节点的父节点，如果p节点的父节点
|
||
在set中，那么这个节点就是最近公共祖先
|
||
*/
|
||
|
||
function f2(root, p, q) {
|
||
const parentMap = new Map(); // 储存父节点映射
|
||
const visited = new Set(); // 记录已访问的节点
|
||
|
||
// 深度优先搜索（DFS）来构建父节点映射
|
||
const dfs = (node) => {
|
||
if (!node) return;
|
||
|
||
if (node.left) {
|
||
parentMap.set(node.left, node); // 记录左节点的父节点
|
||
dfs(node.left); // 继续递归
|
||
}
|
||
|
||
if (node.right) {
|
||
parentMap.set(node.right, node); // 记录右节点的父节点
|
||
dfs(node.right); // 继续递归
|
||
}
|
||
};
|
||
|
||
// 执行DFS来构建父节点映射
|
||
dfs(root);
|
||
|
||
// 追溯p的路径并标记
|
||
while (p) {
|
||
visited.add(p); // 标记p节点
|
||
p = parentMap.get(p); // 跳到p的父节点
|
||
}
|
||
|
||
// 追溯q的路径并查找是否有交点
|
||
while (q) {
|
||
if (visited.has(q)) return q; // 找到交点，返回q
|
||
q = parentMap.get(q); // 跳到q的父节点
|
||
}
|
||
|
||
return null; // 如果没有交点，返回null
|
||
}
|