[LeetCode][JavaScript]Lowest Common Ancestor of a Binary Search Tree

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的路径，比较路径输出不同的那个节点。

/**
 * 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 pathP = [];
    var pathQ = [];
    findLCA(root, p.val, pathP);
    findLCA(root, q.val, pathQ);
    var len = Math.min(pathP.length, pathQ.length);
    for(var i = 0; i <= len; i++){
        if(!pathP[i] || !pathQ[i] || pathP[i].val !== pathQ[i].val){
            return pathP[--i];
        }
    }

    function findLCA(node, target, list){
        list.push(node);
        if(target < node.val){
            findLCA(node.left, target, list);
        }else if(target > node.val){
            findLCA(node.right, target, list);
        }
    }
};

 

 

第一遍写了这么个破东西。

先看左子树里有没有其中一个，如果有先记下，然后看右子树里有没有，加上左子树的结果判断是否找到，

最后加上目前节点的val，看是否找到。

虽然一轮遍历就可以知道结果，但是超级复杂，写了好长，没有用到BST的性质...

/**
 * 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 target = [], res, isFound = false;
    target.push(p.val);
    target.push(q.val);
    findLCA(root);
    return res;

    function findLCA(node){
        if(isFound){
            return [];
        }

        var candidates = [];
        if(node.left !== null){
            var left = findLCA(node.left);
            left = compareVal(left);
            if(left === true){
                res = node.left;
                isFound = true;
                return [];
            }else if(left.length === 1){
                candidates= left;
            }
        }

        if(node.right !== null && !isFound){
            var right = findLCA(node.right);
            if(right && right.length === 1){
                candidates.push(right[0]);
            }
            right = compareVal(candidates);
            if(right === true){
                res = node;
                isFound = true;
                return [];
            }else if(right.length === 1){
                candidates = right;
            }
        }
        
        if(!isFound){
            candidates.push(node.val);
            var curr = compareVal(candidates);
            if(curr === true){
                res = node;
                isFound = true;
                return [];
            }
            return curr;
        }
        
    }
    function compareVal(a, b){
        if(typeof a === "object"){
            if(a.length === 2){
                b = a[1];
                a = a[0];
            }else if(a.length === 1){
                a = a[0];
            }
        }
        var index1 = target.indexOf(a);
        var index2 = target.indexOf(b);
        if(index1 !== -1 && index2 !== -1 && (index1 !== index2 || a === b)){
            return true;
        }else{
            if(index1 !== -1){
                return [a];
            }else if(index2 !== -1){
                return [b];
            }
        }
        return [];
    }
};