Share my C++ solution within 40 ms with explanation


  • 1
    Y
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<int> pPath, qPath;
            TreeNode *pointer = root;
            // Get the path to p
            while(pointer->val != p->val) {
                if(pointer->val > p->val) {
                    pPath.push_back(0);
                    pointer = pointer->left;
                }
                else {
                    pPath.push_back(1);
                    pointer = pointer->right;
                }
            }
            pointer = root;
           // Get the path to q
            while(pointer->val != q->val) {
                if(pointer->val > q->val) {
                    qPath.push_back(0);
                    pointer = pointer->left;
                }
                else {
                    qPath.push_back(1);
                    pointer = pointer->right;
                }
            }
            pointer = root;
            for(int i = 0; i < pPath.size() && i < qPath.size(); i++) {
                // q and q belongs to the different child of pointer, so pointer is the LCA
                if(pPath[i] != qPath[i])
                    return pointer;
                else {// Go to the left child of pointer
                    if(pPath[i] == 0)
                        pointer = pointer->left;
                    else // Go to the right child of pointer
                        pointer = pointer->right;
                }
            }
            // One is the ancestor of the other
            return pointer;
        }
    };

  • 0
    A
    if (p==NULL )
    {
    return q;
    }
    if (q==NULL )
    {
    	return p;
    }
    TreeNode* ancestor=root;
    while (ancestor!=NULL)
    {
    	if (ancestor->val>p->val&&ancestor->val>q->val)
    	{
    		ancestor = ancestor->left;
    		
    	}
    	else if (ancestor->val<p->val&&ancestor->val<q->val)
    	{
    		ancestor= ancestor->right;
    	}
    	else{break;}
    	
    }
    
    return parent;

Log in to reply
 

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