Finding the nearest common ancestor of binary search tree by recursion

235. The nearest common ancestor of a binary search tree

difficulty ： Simple

Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .

Baidu Encyclopedia The definition of the most recent common ancestor in is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Ideas

This problem must be used well BST Properties of trees ！

There are three situations

• Both nodes are smaller than the current node , Are all on the left subtree of the current node
• Both nodes are larger than the current node , Are all on the right subtree of the current node
• One is larger than the current node （ Or equal to ）, One is smaller than the current node （ Or equal to ）, Then the current node is the nearest common ancestor of the two nodes

Using recursion is easy

package cn.edu.xjtu.carlWay.tree.commonAncestorBST;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 235.  The nearest common ancestor of a binary search tree  *  Given a binary search tree ,  Find the nearest common ancestor of the two specified nodes in the tree . * <p> *  In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree  T  Two nodes of  p、q, Recently, the common ancestor is represented as a node  x, Satisfy  x  yes  p、q  Our ancestors and  x  As deep as possible （ A node can also be its own ancestor ）. * <p> * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ */
public class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        // case 1
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        // case 2
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        // case 3
        return root;
    }
}