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

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) {
        // 二叉搜索树的特点：左子树的所有节点值小于根节点值；右子树的所有节点值大于根节点值；中序遍历的结果是一个有序数组。
        //最近的公共祖先（LCA）：
        //1. p<cur.val && q<cur.val --> LCA在cur节点的左子树中；
        //2. p>cur.val && q>cur.val --> LCA在cur节点的右子树中
        //3. p<cur.val && q>cur.val --> LCA即为cur
        //遍历以上直到找到LCA
        //Note：如果当前节点为null，返回null
        //      如果当前节点为p或者q，直接返回当前节点
        if(root == null){
            return -1;
        }

        //判断p和q节点与当前节点值的大小
        if(p < root.val && q < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }

        if(p > root.val && q > root.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        

        return root.val;
    }
}

解决思路：对于找公共祖先的题目，一定要先了解二叉搜索树的性质：1. 左子树的所有节点值小于根节点值；2. 右子树的所有节点值大于根节点值；3. 中序遍历的结果是一个有序数组。基于此类特性，所以寻找q和p的公共祖先位置时，可以利用节点值大小的关系来确定。

算法思路：

1. 当 p<cur.val && q<cur.val --> p和q都在cur节点的左子树中，公共祖先也在左子树中。

2. 当 p>cur.val && q>cur.val --> p和q都在cur节点的右子树中，公共祖先也在右子树中。

3. 当p>cur.val && q<cur.val（或者 p<cur.val && q>cur.val) --> p和q分别在cur的左右子树中，即当前节点cur为公共祖先。

4. 当 p/q = cur.val 时，当前节点即为公共祖先节点。

因此按照这个思路进行代码实现即可。