JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Example 1:

img

Input: tree = [2,1,3], node = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.

Example 2:

img

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -10^5 <= Node.val <= 10^5
  • All Nodes will have unique values.

Code

285 450

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node node) {
        // 1. find min in right
        if(node.right != null) {
            Node curr = node.right;
            while(curr.left != null) {
                curr = curr.left;
            }
            
            return curr;
        }
        
        // 2. no right, check parent
        Node curr = node.parent;
        
        while(curr != null) {
            if(curr.left == node) {
                return curr;
            }
            
            node = curr;
            curr = curr.parent;
        }
        
        return  null;
    }
}

class Solution {
    public Node inorderSuccessor(Node node) {
        if(node == null) return null;
        
        if(node.right != null) {
            Node right = node.right;
            
            while(right.left != null) {
                right = right.left;
            }

            return right;
        } 
        
        Node parent = node.parent;
        
        while(parent != null && parent.val < node.val) {
            parent = parent.parent;
        }

        return parent;
    }
}