Non-recursive, iterative, C++ concise code with comments.


  • 0
    S
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
            
            while(root)// this also covers corner condition when root is nullptr
            
                if(root->val>max(p->val,q->val))// ancestor is in the left
                root=root->left;
                else if(root->val<min(p->val,q->val))// ancestor is in the right
                root=root->right;
                else// ancestor is found
                break;
            
            return root;
            
        }
    };

  • 0
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
            while(true)
    
                if(root->val>max(p->val,q->val))// ancestor is in the left
                    root=root->left;
                else if(root->val<min(p->val,q->val))// ancestor is in the right
                    root=root->right;
                else// ancestor is found or the root is nullptr
                    return root;
        }
    };

Log in to reply
 

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