Leetcode skimming: binary tree 25 (the nearest common ancestor of binary search tree)

235. The nearest common ancestor of a binary search tree

Force button topic link

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

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 ）.”

for example , Given the following binary search tree : root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

• Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
• Output : 6
• explain : node 2 And nodes 8 The most recent public ancestor of 6.

Example 2:

• Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
• Output : 2
• explain : node 2 And nodes 4 The most recent public ancestor of 2, Because by definition, the nearest common ancestor node can be the node itself .

This problem can also be done by using the general method in my last section , It's just a binary search tree , Orderly , It can be done according to the nature . nature ： Orderly （ The decreasing ）

package com.programmercarl.tree;

/** * @ClassName BstLowestCommonAncestor * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 12:36 * @Version 1.0 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/ * 235.  The nearest common ancestor of a binary search tree  **/
public class BstLowestCommonAncestor {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        // Because it's orderly , Just find the node closest to the two elements 
        //  The template node is on the left of the current node 
        if (root.val > p.val && root.val > q.val) {
    
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
    
            root = root.right;
        } else {
    
            //root Between the two nodes , It's a closed interval . And it's  [p,q] The closed interval of , No  p  Namely  q
            // Because it moves step by step , So it's the critical point 
            return root;
        }
        return lowestCommonAncestor(root, p, q);
    }
}