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; };
[LeetCode]Lowest Common Ancestor of a Binary Search Tree
原文：http://www.cnblogs.com/agentgamer/p/5369574.html