思路：

递归二叉树，递归查找每个节点左右子树是否含有o1、o2节点

  • 情况一：当前节点为空，返回-1
  • 情况二：当前节点为其中一个节点，返回该节点
  • 情况三：左右子树都未找到
  • 如果 left 和 right 都等于 -1，说明 o1 和 o2 都不在当前节点的左右子树中，当前子树无法提供 o1 和 o2 的最近公共祖先信息，返回 -1。
  • 情况四：左右子树其中之一找到
  • 若 left 等于 -1，而 right 不等于 -1，这表明 o1 和 o2 都不在左子树中，它们都在右子树里，所以最近公共祖先就在右子树中，返回 right。
  • 当 right 等于 -1，而 left 不等于 -1 时，说明 o1 和 o2 都不在右子树中，它们都在左子树里，因此最近公共祖先就在左子树中，返回 left。
  • 情况五：左右子树都找到部分信息
  • 如果 left 和 right 都不等于 -1，这意味着 o1 和 o2 分别在当前节点的左子树和右子树中，那么当前节点就是它们的最近公共祖先，返回当前节点的值 root.val。

import java.util.*;
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 节点为空返回-1
        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);
        // o1,q都不在root的左右子树中，返回-1
        if (left == -1 && right == -1) {
            return -1;
        }
        // 如果 o1 和 o2 只有一个存在于 root 为根的树中，函数返回该节点
        if (left == -1) {
            return right;
        }
        if (right == -1) {
            return left;
        }
        // 如果 o1 和 o2 都在以 root 为根的树中，那么 left 和 right 一定分别是 o1 和 o2
        return root.val;
    }
}