40ms iterative c++ solution with clear explanaton


  • 2
    C
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            // suppose p <= q
            // LCA_BST(root, p, q) = 
            // if p<=root<=q. root
            // if root<p. LCA_BST(root->right, p, q)
            // if root>q. LCA_BST(root->left, p, q)
            
            if(!p) return q;
            if(!q) return p;
            
            if(p->val > q->val)
            {
                TreeNode *tmp = p;
                p = q;
                q = tmp;
            }
            
            TreeNode *iter = root;
            
            while(iter)
            {
                if(iter->val < p->val)      iter = iter->right;
                else if(iter->val > q->val) iter = iter->left;
                else                        return iter;
            }
            
            return NULL;
        }
    };

Log in to reply
 

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