剑指offer26 JZ68 二叉搜索树的最近公共祖先

思路

我们也可以利用二叉搜索树的性质：对于某一个节点若是p与q都小于等于这个这个节点值，说明p、q都在这个节点的左子树，而最近的公共祖先也一定在这个节点的左子树；若是p与q都大于等于这个节点，说明p、q都在这个节点的右子树，而最近的公共祖先也一定在这个节点的右子树。而若是对于某个节点，p与q的值一个大于等于节点值，一个小于等于节点值，说明它们分布在该节点的两边，而这个节点就是最近的公共祖先，因此从上到下的其他祖先都将这个两个节点放到同一子树，只有最近公共祖先会将它们放入不同的子树，每次进入一个子树又回到刚刚的问题，因此可以使用递归。

递归

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

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

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

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

步骤

• step 1：首先检查空节点，空树没有公共祖先。
• step 2：对于某个节点，比较与p、q的大小，若p、q在该节点两边说明这就是最近公共祖先。
• step 3：如果p、q都在该节点的左边，则递归进入左子树。
• step 4：如果p、q都在该节点的右边，则递归进入右子树。

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 p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here 
    //空树
        if(root==null){
            return -1;
        }
        //根节点在为root;
         if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val)){
            return root.val;
            
        }
        else if(p <= root.val && q <= root.val){
            //pq都在该节点的左边
            return lowestCommonAncestor(root.left,p, q);
        }else{
            //pq都在该节点的右边
            return lowestCommonAncestor(root.right,p,q);
        }
    }
}