C++, dfs, not the best solution but easy to understand.


  • 1
    Y
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            foundP = false;
            foundQ = false;
            ret = NULL;
            dfs(root,p,q);
            return ret;
        }
    private:
        bool foundP;
        bool foundQ;
        TreeNode *ret;
    
        void dfs(TreeNode *root, TreeNode *p, TreeNode *q){
            if(root == NULL) return;
            bool state1 = foundP || foundQ;
            dfs(root->left,p,q);
            bool state2 = foundP ^ foundQ;
            dfs(root->right,p,q);
            bool state3 = foundP ^ foundQ;
    
            if(root == p) foundP = true;
            if(root == q) foundQ = true;
            bool state4 = foundP && foundQ;
    
            if(!state1 && state2 && !state3) ret = root;
            else if(!state1 && state3 && state4) ret = root;
        }
    };
    

    I use 4 states to trace the dfs() process:

    • State1: Before visit left child and right child
    • State2: After finished dfs(left child)
    • State3: After finished dfs(two children)
    • State4: After dfs children, check root itself.

    When can we judge that root is the ancestor?

    ##[1] root isn't one of (p,q)

    • State1: Before visit left child and right child, found neither p nor q
    • State2: Found one of p,q in dfs(left child): foundP == 0 && foundQ == 1 or foundP == 1 && foundQ ==0 equals to foundP ^ foundQ
    • State3: Found another in dfs(right child): foundP == 1 && foundQ == 1

    e.g. tree = [1, 2 ,3]; p = 2; q = 3

    ##[2] root is one of (p,q) or root == p == q

    • State1: found none of (p,q)
    • State2: we don't care.
    • State3: After State3, only one of (p,q) is found OR None of them is found.
    • State4: We check the value of root, and it equals to one of (p,q) OR both of p and q.
      By now we have found p and q.

    e.g. tree = [1,2]; p = 1; q = 2


    ###This solution can be optimized, but this version is clear. Hope this helps :)


    *Another solution, using extra vector to save path

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            vector<TreeNode*> pPath,qPath;
            bool foundP = findPath(root,p,pPath);
            bool foundQ = findPath(root,q,qPath);
            if(!foundP && !foundQ) return NULL;
            int loop = 0;
            while(loop<pPath.size()&&loop<qPath.size()&&pPath[loop]==qPath[loop]) loop++;
            if(pPath[loop-1]!=qPath[loop-1]) return NULL;
            else return pPath[loop-1];
        }
        
    private:
        bool findPath(TreeNode *root, TreeNode *find, vector<TreeNode*>& savePath){
            if(root==NULL) return false;
            savePath.push_back(root);
            if(root == find) return true;
            if(findPath(root->left,find,savePath)) return true;
            if(findPath(root->right,find,savePath)) return true;
            savePath.pop_back();
            return false;
        }
    };

Log in to reply
 

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