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

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    
    public TreeNode find(TreeNode t,int o1,int o2){
        if(t==null || t.val==o1 || t.val==o2) return t;
        TreeNode left = find(t.left,o1,o2);
        TreeNode right = find(t.right,o1,o2);
        if(left==null) return right;
        if(right==null) return left;
        return t;

    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return find(root,o1,o2).val;
    }
}

递归情况：

1.当到达空节点时，直接返回空

2.当root等于 o1 或 o2 时，返回root

3.若不为1， 2中情况，说明需要继续处理：

对左子树进行递归，返回值记为 t1

对右子树进行递归，返回值记位 t2

t1 ，t2 存在以下几种情况：

①. 当t1, t2都为空时，说明root的左右子树中都不存在o1, o2， 返回空

②. 当t1为空且t2不为空时，说明左子树找不到 o1, o2,所以返回在右子树查找后的结果 即t2

③. 当t2为空且t1不为空时，说明右子树找不到 o1, o2,所以返回在左子树查找后的结果 即t1

④. 当t1, t2都不为空时,说明o1, o2分别位于当前root结点的左右子树中，既root为答案，返回root