The nearest common ancestor of a binary search tree

Leetcode-cn.com/problems/lo…

Their thinking

They’re giving us a binary search tree, so it’s smaller on the left and bigger on the right. Using this feature, you can compare the values of the two nodes given to the root node, thus determining the approximate location of the common ancestor.

• Both nodes have values less than the root node, so they’re both on the left subtree, and the common ancestor should also be on the left.

• Both nodes have values greater than the root node, so they’re both on the right subtree, and the common ancestor should also be on the right.

• One is larger than the root and one is smaller than the root, so the nearest common ancestor must be on the root.

The following code

/** * 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);
        returnroot; }}Copy the code