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

LeetCode 235

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

解题思路

题目给的是二叉搜索树，所以满足左小右大。
利用这一特性，可以把给的两个节点的值和根节点作比较，这样可以确定公共祖先的大致位置。

• 两个节点的值都小于根节点，所以他们都在左子树上，公共祖先也应该在左边找。

• 两个节点的值都大于根节点，所以他们都在右子树，上公共祖先也应该在右边找。

• 两个节点一个大于根节点，一个小于根节点，所以最近公共祖先肯定在根节点上。

代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}