235. Lowest Common Ancestor of a Binary Search Tree
先用最ugly 最随心所欲的代码AC,基本思想是生成两个路径,然后找到最后一个相同的值,然后在BST中查找到这个值返回结点地址,最直观,最容易理解,代码相对啰嗦。

/**
 * 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) {
        vector<int> m,n;
        TreeNode * pp = root,*qq = root;
        while(pp)
        {
            m.push_back(pp->val);
            if(pp->val > p->val)
                pp = pp->left;
            else if (pp->val < p->val)
                pp = pp->right;
            else
                break;
        }
        
        while(qq)
        {
            n.push_back(qq->val);
            if(qq->val > q->val)
                qq = qq->left;
            else if (qq->val < q->val)
                qq = qq->right;
            else
                break;
        }

        int res;
        for(int i = 0;i<min(m.size(),n.size());i++)
        {
            
            if(m[i] != n[i])
            {
                break;
            }
            
            res = m[i];
        }
        
        while(root)
        {
            if(root->val == res)
                return root;
            else if (root->val < res)
                root = root->right;
            else 
                root = root->left;
        }

        return NULL;
    }
};

运行效率:

Runtime: 32 ms, faster than 88.46% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 42.56% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.

第一版代码相对啰嗦,我们优化后的代码如下:

/**
 * 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 {
private:
    TreeNode * generate_path(vector<int> & path,TreeNode *root,TreeNode *target)
    {
        while(root)
        {
            path.push_back(root->val);
            if(root->val > target->val)
                root = root->left;
            else if (root->val < target->val)
                root = root->right;
            else
                break;
        }
        
        return root;
    }
    
    TreeNode * search_target(TreeNode *root,int target)
    {
        while(root)
        {
            if(root->val > target)
                root = root->left;
            else if (root->val < target)
                root = root->right;
            else
                break;
        }
        
        return root;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<int> ppath,qpath;
        int target;
        TreeNode * pp = generate_path(ppath,root,p);
        TreeNode * qq = generate_path(qpath,root,q);
    
        for(int i = 0;i<min(ppath.size(),qpath.size());i++)
        {
            if(ppath[i] != qpath[i])
            {
                break;
            }
            target = ppath[i];
        }
        
        return search_target(root,target);
    }
};

运行结果:

Runtime: 32 ms, faster than 88.16% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.

上面的代码似乎很冗余,但是却非常好理解,在讨论区看到大神们的解法,可以说是非常high level了,利用二叉搜索树的特性:左子树 < 根节点 < 右子树

/**
 * 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) {
        if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right,p,q);
        else if (root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left,p,q);
        else 
            return root;
    }
};

运行结果:

Runtime: 24 ms, faster than 99.43% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Next challenges:

非递归版本:

/**
 * 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) {
        while(root)
        {
            if(root->val < p->val && root->val < q->val)
                root = root->right;
            else if (root->val > p->val && root->val > q->val)
                root = root->left;
            else 
                return root;
        }
        
        return NULL;
    }
};

运行结果:

Runtime: 32 ms, faster than 88.16% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.8 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.