题解 | #二叉搜索树的最近公共祖先#

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

        if (root == null) {
            return -1;
        }

        if ( (p <= root.val && q >= root.val) || (q <= root.val && p >= root.val)) {
            return root.val;
        }

        if (p <= root.val && q <= root.val) {
            return  lowestCommonAncestor ( root.left,  p,  q);
        } else {
            return  lowestCommonAncestor ( root.right,  p,  q);
        }

    }

}