*题解 | #在二叉树中找到两个节点的最近公共祖先#

• 递归法寻找公共祖先

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return commonAncestor(root,  o1,  o2)->val;
    }
    
    TreeNode* commonAncestor(TreeNode* root, int o1, int o2){
        if(!root) return nullptr;
        if(root->val == o1 || root->val == o2)
            return root;
        TreeNode* left = commonAncestor(root->left, o1, o2);
        TreeNode* right = commonAncestor(root->right, o1, o2);
        if(!left) return right; //两个节点都在右侧 
        if(!right) return left;//两个节点都在左侧
        return root; //left和right都不为空时，说明这个节点是公共祖先节点
    }
};