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

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 {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // 递归实现，终止条件
        if(root==null){
            return -1;
        }
        if(root.val==o1){
            return o1;
        }
        if(root.val==o2) return o2;

// 开始递归
        // 左子树右子树的最近公共祖先，也相当于找一棵树的最近公共祖先
        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;
    }
}