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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        //二叉树的每一条从根到叶子节点的路径，可以看成一条链表，
        //这样，本题就变成求解两个链表的第一个公共节点。

        //基于二叉树的特点，如果o1和o2分属root的左右两边，则root就是它们的最近公共祖先

        //因此，二叉树的公共祖先类别的题目都有这个特性。，所以可以依次递归进入左右子树来判断
        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;
    }
}