剑指offer25 JZ86 在二叉树中找到两个节点的最近公共祖先

思路

要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下

递归

分析可知，对于节点 o1, o2 的最近公共祖先，只存在三种情况：

o1 ，o2 分别位于root的左右子树上

o1 = root, 且 o2 位于root的左子树/右子树中

o2 = root, 且 o1 位于root的左子树/右子树中

• 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

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 int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return last(root,o1,o2).val;
    }
    public TreeNode last(TreeNode node,int o1,int o2){
       //如果根节点为空 或者只有一个有值 返回根节点
        if(node==null|| node.val==o1||node.val==o2){
            return node;
        }
        //递归左子树
        TreeNode left=last(node.left,o1,o2);
        //递归有子树
        TreeNode right=last(node.right,o1,o2);
        if(left==null){
        
//             左子树为空结果在右子树上
            return right;
        }
        if(right==null){
//             右子树为空结果在左子树上
            return left;
        }
         //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
    //我们只需要返回cur结点即可。
        return node;
    }
}