[LeetCode]Lowest Common Ancestor of a Binary Search Tree

时间:2020-12-05 07:50:05

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Subscribe to see which companies asked this question.

简单题,不过加上思考和编码的时间也大概有半小时了吧。。。

思路就是使用dfs,分别dfs 寻找两个数,记录下从root 到目标node 经过了哪些node,如果在某一次dfs 中发现了存在的node 就说明那个node就是LCA。关键在于,要在递归后检查,而不是在递归前,这样才能保证是lowest 的,因为整个检查过程是倒桩的。如果是在递归前检查,就变成最高祖先了(root)。

/**
* 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}
*/
var lowestCommonAncestor = function(root, p, q) {
var _lca = null;
var _set = {};
function dfs(node, a, set) {
if (!node) return;
if (node.val == a) {
if (set[node.val] != void 0 && _lca === null) _lca = node;
else set[node.val] = 1;
return a;
}
var l_find = dfs(node.left, a, set);
if (l_find == a) {
if (set[node.val] != void 0 && _lca === null) _lca = node;
else set[node.val] = 1;
return a;
}
var r_find = dfs(node.right, a, set);
if (r_find == a) {
if (set[node.val] != void 0 && _lca === null) _lca = node;
else set[node.val] = 1;
return a;
}
} dfs(root, p.val, _set);
dfs(root, q.val, _set); return _lca;
};