力扣-二叉树-236 二叉树的最近公共祖先

思路1

后序遍历，然后根据根节点是否所寻找的节点，然后再满足最大深度时再更新result即可

代码1

class Solution {
public:
    int maxDeepth = 0;
    int count;
    TreeNode* result;// p=1 q=2
    int backTravesl(TreeNode* node, TreeNode* p, TreeNode* q, int curDeepth){
        if(node == NULL) return 0;
        int left = backTravesl(node->left, p, q, curDeepth+1);
        int right = backTravesl(node->right, p, q, curDeepth+1);

        if(node == p || node == q){
            if(left + right == 1 && curDeepth >= maxDeepth){
                result = node;
                maxDeepth = curDeepth;
            }
            return 1 + left + right;
        } 
        if(left + right == 2 && curDeepth >= maxDeepth){
            result = node;
            maxDeepth = curDeepth;
        }
        return left + right;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        backTravesl(root, p, q, 1);

        return result;
    }
};

思路2

当前节点如果是p或q，直接返回，这样如果当前节点下有另一个p或q，符合题意，如果没有，就退化成第一种p和q在左右的情况了

代码2

class Solution {
public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;
        if(root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left != NULL && right != NULL) return root;
        else if(left != NULL && right == NULL) return left;
        else if(left == NULL && right != NULL) return right;

        return NULL;
    }
};