A clean and efficient C++ solution.


  • 3
    S

    My C++ solution is as follow, very simple and easy to understand.

    In general, it is based on the basic searching on BST and comparing pointers. That's all.

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if ( !root || !p || !q ) { return NULL; }
        TreeNode* ans = root;
        TreeNode* r = root; // for search node p
        TreeNode* k = root; // for search node q
        while ( r != p || k != q ) {
            if ( p->val < r->val ) {
                r = r->left;
            } else if ( p->val > r->val ) {
                r = r->right;
            }
            if ( q->val < k->val ) {
                k = k->left;
            } else if ( q->val > k->val ) {
                k = k->right;
            }
    
            if ( r == k ) {
                ans = r;
            } else {
                break;
            }
        }
    
        return ans;
    }

  • 0
    V

    Thanks for sharing. It is impressive.


  • 0
    B

    nice solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.