[NC]102. 二叉树中找两个节点的最近公共祖先

🚩传送门：牛客题目

题目

树中一定存在公共祖先
给定一棵二叉树(保证非空)以及这棵树上的两个节点的 val 值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

示例 1:

输入: [3,5,1,6,2,0,8,#,#,7,4],5,1 输出: 3

解题思路：递归

我的代码

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 1. root为空则不存在,返回-1
        if(root == null) return -1;
        // 2. 如果root为o1或o2中任意一个，则root就是公共祖先
        if(root.val == o1 || root.val == o2) return root.val;
        // 3. root不为o1或o2
        int left = lowestCommonAncestor(root.left, o1, o2); // 递归遍历左子树，只要在左子树中找到了o1或o2，则先找到谁就返回谁
        int right = lowestCommonAncestor(root.right, o1, o2);
        // 如果 left=-1，说明在左子树中一直找到叶子节点，也没找到o1或者o2
        if(left == -1) return right;    // 所以最近公共祖先，必在右子树中，且right中第一个找的o1或者o2即为最近公共祖先
        // 如果 right=-1，说明在右子树中一直找到叶子节点，也没找到o1或者o2
        if(right == -1) return left;    // 所以最近公共祖先，必在左子树中，且left中第一个找的o1或者o2即为最近公共祖先
        // 若left和right都不为-1，则说明o1,o2节点在root的异侧，则root为最近公共祖先
        return root.val;
    }
}