A review of top solutions


  • 1
    1. Iterative solution. Lca is determined by going up from p and q, if each node has a pointer to parent. So the intuition is to compute the child to parent mapping. The great idea is from @dietpepsi
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            unordered_map<TreeNode*,TreeNode*> parent({{root,NULL}});
            stack<TreeNode*> stk({root});
            while(!parent.count(p) || !parent.count(q)) {
                TreeNode *n = stk.top();
                stk.pop();
                if(n->left) {
                    parent[n->left] = n;
                    stk.push(n->left);
                }
                if(n->right) {
                    parent[n->right] = n;
                    stk.push(n->right);
                }
            }
            unordered_set<TreeNode*> path;
            while(p) {
                path.insert(p);
                p = parent[p];
            }
            while(!path.count(q)) q = parent[q];
            return q;
        }
    

    The above solution back tracks from p first and then q. If the lca is low, then it is not very efficient. We can back track from p and q similtaneously instead.

            unordered_set<TreeNode*> pp, pq;
            while(p||q) {
                if(p) {
                    if(pq.count(p)) return p;
                    pp.insert(p);
                    p = parent[p];
                }
                if(q) {
                    if(pp.count(q)) return q;
                    pq.insert(q);
                    q = parent[q];
                }
            }
            return NULL;
    
    1. Recursion. If p or q is found, return it. If found none, return NULL. If p and q are found in left and right subtree, return root(lca). The great idea is from @StefanPochmann
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root||root==p||root==q) return root;
            auto l = lowestCommonAncestor(root->left, p, q);
            if(l && l!=p && l!=q) return l;
            auto r = lowestCommonAncestor(root->right, p, q);
            return !l?r:!r?l:root;
        }
    

Log in to reply
 

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