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

• step 1：如果o1和o2中的任一个和root匹配，那么root就是最近公共祖先。

• step 2：如果都不匹配，则分别递归左、右子树。

• step 3：如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.

• step 4：如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

• step 5：继续递归左、右子树，直到遇到step1或者step3的情况。

int lowestCommonAncestor(struct TreeNode* root, int o1, int o2 ) {
    // write code here
    if(root==NULL){
        return -1;
    }
    if(root->val==o1 || root->val==o2){
        return root->val;
    }
    int left=lowestCommonAncestor(root->left, o1, o2);
    int right=lowestCommonAncestor(root->right, o1, o2);
    if(left==-1){//左边没找到任何相同，那么一定在右边
        return right;
    }
    if(right==-1){//右边没有找到任何相同，则一定在左边
        return left;
    }
    return root->val;//左右都找到了，那说明当前root是最近公共祖先
}