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.
我的想法是红选，找到這個(gè)兩個(gè)元素护侮，并把從根節(jié)點(diǎn)到這兩個(gè)元素的路記下來(lái)萤悴，這個(gè)路上第一個(gè)相同的元素就是最低的共同祖先问词。
/**
* 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 findNode = function(root,node,record){
if (root===null) {
return false;
}
if (root===node) {
record.push(root);
return true;
}
if (findNode(root.left,node,record)) {
record.push(root);
return true;
}
if (findNode(root.right,node,record)) {
record.push(root);
return true;
}
}
if (root!==null&&p!==null&&q!==null) {
if (p===q) {
return q;
}
var record1 = [];
var record2 = [];
findNode(root,p,record1);
findNode(root,q,record2);
//console.log(record1);
//console.log(record2);
for (var i = 0; i<record1.length; i++) {
for (var j = 0; j<record2.length; j++) {
//console.log(record1[i]+"&&&"+record2[j]);
if (record1[i]===record2[j]) {
return record1[i];
}
}
}
}
};
但是這個(gè)方法好慢的樣子。题造。。暫時(shí)沒(méi)有想到別的方法亚再。
