[LeetCode][JavaScript]Lowest Common Ancestor of a Binary Search Tree
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][JavaScript]Lowest Common Ancestor of a Binary Search Tree，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3474字，纯文字阅读大概需要5分钟。
内容图文
Lowest Common Ancestor of a Binary Search Tree
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.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
传说中的经典问题...经典解法：
2轮遍历，记录下p和q的路径，比较路径输出不同的那个节点。
1
/*
*
2
* Definition for a binary tree node.
3
* function TreeNode(val) {
4
* this.val = val;
5
* this.left = this.right = null;
6
* }
7
*/
8
/*
*
9
* @param {TreeNode} root
10
* @param {TreeNode} p
11
* @param {TreeNode} q
12
* @return {TreeNode}
13
*/
14
var lowestCommonAncestor = function(root, p, q) {
15var pathP = [];
16var pathQ = [];
17 findLCA(root, p.val, pathP);
18 findLCA(root, q.val, pathQ);
19var len = Math.min(pathP.length, pathQ.length);
20for(var i = 0; i <= len; i++){
21if(!pathP[i] || !pathQ[i] || pathP[i].val !== pathQ[i].val){
22return pathP[--i];
23 }
24 }
2526function findLCA(node, target, list){
27 list.push(node);
28if(target < node.val){
29 findLCA(node.left, target, list);
30 }elseif(target > node.val){
31 findLCA(node.right, target, list);
32 }
33 }
34 };
第一遍写了这么个东西。
先看左子树里有没有其中一个，如果有先记下，然后看右子树里有没有，加上左子树的结果判断是否找到，
最后加上目前节点的val，看是否找到。
虽然一轮遍历就可以知道结果，但是超级复杂，写了好长，没有用到BST的性质...
1
/*
*
2
* Definition for a binary tree node.
3
* function TreeNode(val) {
4
* this.val = val;
5
* this.left = this.right = null;
6
* }
7
*/
8
/*
*
9
* @param {TreeNode} root
10
* @param {TreeNode} p
11
* @param {TreeNode} q
12
* @return {TreeNode}
13
*/
14
var lowestCommonAncestor = function(root, p, q) {
15var target = [], res, isFound = false;
16 target.push(p.val);
17 target.push(q.val);
18 findLCA(root);
19return res;
2021function findLCA(node){
22if(isFound){
23return [];
24 }
2526var candidates = [];
27if(node.left !== null){
28var left = findLCA(node.left);
29 left = compareVal(left);
30if(left === true){
31 res = node.left;
32 isFound = true;
33return [];
34 }elseif(left.length === 1){
35 candidates= left;
36 }
37 }
3839if(node.right !== null && !isFound){
40var right = findLCA(node.right);
41if(right && right.length === 1){
42 candidates.push(right[0]);
43 }
44 right = compareVal(candidates);
45if(right === true){
46 res = node;
47 isFound = true;
48return [];
49 }elseif(right.length === 1){
50 candidates = right;
51 }
52 }
5354if(!isFound){
55 candidates.push(node.val);
56var curr = compareVal(candidates);
57if(curr === true){
58 res = node;
59 isFound = true;
60return [];
61 }
62return curr;
63 }
6465 }
66function compareVal(a, b){
67if(typeof a === "object"){
68if(a.length === 2){
69 b = a[1];
70 a = a[0];
71 }elseif(a.length === 1){
72 a = a[0];
73 }
74 }
75var index1 = target.indexOf(a);
76var index2 = target.indexOf(b);
77if(index1 !== -1 && index2 !== -1 && index1 !== index2){
78returntrue;
79 }else{
80if(index1 !== -1){
81return [a];
82 }elseif(index2 !== -1){
83return [b];
84 }
85 }
86return [];
87 }
88 };
原文：http://www.cnblogs.com/Liok3187/p/4641389.html
内容总结
以上是互联网集市为您收集整理的[LeetCode][JavaScript]Lowest Common Ancestor of a Binary Search Tree全部内容，希望文章能够帮你解决[LeetCode][JavaScript]Lowest Common Ancestor of a Binary Search Tree所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。