[daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree

subject

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 .

explain :
The values of all nodes are unique .
p、q For different nodes and all exist in a given binary search tree .

Code

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

class Solution {
    
    //  At the same time, find the arrival p、q The path of , Find the bifurcation point of two paths , Make full use of the properties of binary search tree 
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        TreeNode ansNode = root;

        while(true){
    
            if(p.val < ansNode.val && q.val < ansNode.val){
    
                ansNode = ansNode.left;
            }
            else if(p.val > ansNode.val && q.val > ansNode.val){
    
                ansNode = ansNode.right;
            }
            //  The path forked , This point is the nearest common ancestor 
            else{
    
                break;
            }
        }

        return ansNode;
    }
}