Easy DFS solution


  • 0
    L
    class Solution {
    private: 
        TreeNode* ret;
        
        //DFS return a 2 bit int indicating if the subtree has p and q
        int lca(TreeNode* root,TreeNode* p, TreeNode* q){
            if(root == NULL) return 0;
            int s = 0;
            if(root == p) s |= 1;
            if(root == q) s |= 2;
            s |= (lca(root->left,p,q) | lca(root->right,p,q));
            if(s == 3 && ret == NULL) ret = root;
            return s;
        }
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root == NULL) return NULL;
            ret = NULL;
            lca(root,p,q);
            return ret;
        }
    };
    

Log in to reply
 

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