235. Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree

原题：235. Lowest Common Ancestor of a Binary Search Tree

时间复杂度：O(n)

Source Code

// Runtime: 168 ms, faster than 5.31% of JavaScript online submissions for Lowest Common Ancestor of a Binary Search Tree.
// Memory Usage: 43.9 MB, less than 20.00% of JavaScript online submissions for Lowest Common Ancestor of a Binary Search Tree.
var lowestCommonAncestor = function(root, p, q) {
    const helper = function(root, p, q) {
        if(q.val<root.val) {
            return helper(root.left, p, q);
        }else if(p.val>root.val) {
            return helper(root.right, p, q);
        }else {
            return root;
        }
    };

    if(p.val>q.val) {
        [p, q] = [q, p];
    }

    return helper(root, p, q);
}

Test Cases

test("test1", ()=>{
    expect(lowestCommonAncestor(makeTree([6,2,8,0,4,7,9,null,null,3,5]), new TreeNode(2), new TreeNode(8)).val).toEqual(6);
})

test("test2", ()=>{
    expect(lowestCommonAncestor(makeTree([6,2,8,0,4,7,9,null,null,3,5]), new TreeNode(2), new TreeNode(4)).val).toEqual(2);
})

236. Lowest Common Ancestor of a Binary Tree

原题：236. Lowest Common Ancestor of a Binary Tree

时间复杂度：O(n)

Source Code

// Runtime: 84 ms, faster than 22.42% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.
// Memory Usage: 41.3 MB, less than 100.00% of JavaScript online submissions for Lowest Common Ancestor of a Binary Tree.
var lowestCommonAncestor = function(root, p, q) {
    const helper = function(root, p, q) {//find p or q
        if(!root || root.val==p.val || root.val==q.val) {
            return root;
        }
        const left = helper(root.left, p, q);
        const right = helper(root.right, p, q);
        
        return left ? (right ? root : left) : right;
    };

    return helper(root, p, q);
}

Test Cases

test("test1", ()=>{
    expect(lowestCommonAncestor(makeTree([3,5,1,6,2,0,8,null,null,7,4]), new TreeNode(5), new TreeNode(1)).val).toEqual(3);
})

test("test2", ()=>{
    expect(lowestCommonAncestor(makeTree([3,5,1,6,2,0,8,null,null,7,4]), new TreeNode(5), new TreeNode(4)).val).toEqual(5);
})