Leetcode brush question diary sword finger offer II 053. Medium order successor in binary search tree

Original link （https://leetcode.cn/problems/P5rCT8）

Title Description

Given a binary search tree and one of its nodes p , Find the sequential successor of this node in the tree . If the node has no middle order successor , Please return null . node p The following is the value ratio p.val The node with the smallest key value among the large nodes , That is, the order nodes traversed in the middle order p The next node of .

Example 1

Input ：root = [2,1,3], p = 1
Output ：2

Example 2

Input ：root = [5,3,6,2,4,null,null,1], p = 6
Output ：nul

Data constraints

• p Is the node of the tree
• The number range of nodes in the number is [1,10^4]
• -10^5 <= Node.val <= 10^5
• The values of each node in the tree are guaranteed to be unique .

Ideas

Binary search tree is a special binary tree , For a node , Its value must be greater than any value of its left subtree , Any value of its right subtree must be greater than it , Several left subtrees < Parent node < Right subtree . It is not necessary to scan every node when using this feature to find a binary tree , Since the topic wants to find the smallest one larger than it, then if you can walk the left subtree, you must walk the left subtree , After walking to the right subtree, you also need to check the left subtree, otherwise it is the right subtree . If the right subtree does not match in the end, then no data matches . At the same time, because the need to match is a tree node , Then if this node has a right subtree, it must be the node from the right subtree to the left subtree , Otherwise, you need to go from the root node .
Such as example 2 The access process of should be
First p No right subtree, all from scratch

Because the value of the root node is less than 6 So you should take the right subtree

Finally get null
Suppose that the example 2 Of p Change it to 3 The result of this node is different
First ,3 There is a right subtree, so you can go through the right subtree

Then the right subtree has no left subtree, so we get 4
Suppose there is a binary search tree, as shown in Figure

hypothesis P by 50
First p There is no right subtree, so you need to start from the root node .
First, the value of the root node is less than 50 So you need to go to the right subtree , Now walk to 65 Node

65 Greater than 50 So you need to go left , But the value of the left subtree is 50 No more than 50 So Zuozi tree also came to the end , So we get the result 65

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 inorderSuccessor(TreeNode root, TreeNode p) {
    
        TreeNode ans = null;
		if (p.right != null) {
    
			ans = p.right;
			while (ans.left != null) {
    
				ans = ans.left;
			}
		}
		while (root != null) {
    
			if (root.val > p.val) {
    
				ans = root;
				root = root.left;
			} else {
    
				root = root.right;
			}
		}
		return ans;
    }
}