235 - 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.

Hide Tags

 Tree

Hide Similar Problems

 (M) Lowest Common Ancestor of a Binary Tree

用了两个解法，

一个是基于BST，

判断root的value是否大于最小值或者小于最大值以剪枝

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        int max = ((p->val)>(q->val))?(p->val):(q->val);

        int min = ((p->val)<(q->val))?(p->val):(q->val);

        

        return dfs(root, min, max);

    }

    

    TreeNode* dfs(TreeNode* root, int min, int max) {

        if(max<(root->val))

            return dfs(root->left, min, max);

        if(min>(root->val))

            return dfs(root->right, min, max);

            

        return root;

    }

};

另一个是无视BST，直接查找指定的p，q，

class Solution {

public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if((root==p)||(root==q)||(NULL==root))

            return root;

        

        TreeNode* ll = lowestCommonAncestor(root->left, p, q);

        TreeNode* rr = lowestCommonAncestor(root->right, p, q);

        

        if(ll&&rr)

            return root;

        

        return ll?ll:rr;

    }

};

测试的结果是，两个方法的耗时都是40ms，直觉上第一种应该更快一点啊。