lowest common ancestor

lca的dfs做法，含判断p q存在性。

class Solution {
    pair<TreeNode*, int> helper(TreeNode * root, TreeNode * p, TreeNode *q) {
        if(root == NULL) return {NULL, 0};
        auto l = helper(root->left, p, q);
        if(l.first && l.second == 2) { return l;}
        auto r = helper(root->right, p,q);
        if(r.first && r.second == 2) { return r;}
        int count = l.second + r.second;
        if(root == p || root == q) { count++; return {root,count};}
        if(count == 2) {return {root, count};}
        if(l.second == 1) {return l;}
        if(r.second == 1) {return r;}
        return {NULL, 0};
    }
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        auto res = helper(root, p, q);
        if(res.second == 2) {return res.first;}
        return NULL;
    }
};

不含判断：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || p == NULL || q == NULL) return NULL;
        if(root == p || root == q) return root;
        TreeNode * l = lowestCommonAncestor(root->left, p, q);
        TreeNode * r = lowestCommonAncestor(root->right, p, q);
        if(l && r) return root;
        if(l) return l;
        if(r) return r;
        return NULL;        
    }
};