Sword finger offer II 053. Medium order successor in binary search tree (medium binary search tree DFS)

The finger of the sword Offer II 053. Middle order successor in binary search tree

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
explain ： here 1 The middle order of is followed by 2. Please note that p And the return value should be TreeNode type .
Example 2：

Input ：root = [5,3,6,2,4,null,null,1], p = 6
Output ：null
explain ： Because the given node has no middle order successor , So the answer goes back to null 了 .

Tips ：

The number of nodes in the tree is in the range [1, 104] Inside .
-105 <= Node.val <= 105
The values of each node in the tree are guaranteed to be unique .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/P5rCT8
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Using the characteristics of binary search tree , The values of the nodes on the left subtree of a node of the tree are smaller than those of the current node , The value of the node on the right subtree is greater than that of the current node , Then just keep following p Compare the values of and consider whether to traverse left or right .

Answer key （Java）

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