NC102：二叉树最近公共祖先

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // root为空则说明越过了叶子节点
        if(root == null) return -1;
        // 如果root为o1或o2中任意一个，则root就是公共祖先
        if(root.val == o1 || root.val == o2) return root.val;

        //root不为o1或o2
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);
        //如果left=-1，说明在左子树中一直找到叶子节点，也没找到最近公共祖先
        //所以最近公共祖先，必在右子树中，right即为最近公共祖先
        if(left == -1) return right;
        //同理，最近公共祖先必在左子树中，left即为最近公共祖先
        else if(right == -1) return left;
        //若left和right都不为-1，则说明o1,o2节点在root的异侧，则root为最近公共祖先
        else return root.val;
    }
}