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;
}
};
