LC: 510. Inorder Successor in BST II
https://leetcode.com/problems/inorder-successor-in-bst-ii/
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:
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:
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.Example 3:
Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15
Output: 17Example 4:
Example 5:
Constraints:
The number of nodes in the tree is in the range
[1, 104].-105 <= Node.val <= 105All Nodes will have unique values.
Follow up: Could you solve it without looking up any of the node's values?
The Essence:
Für dieses Problem sollen die Traversierungsalgorithmen bei dem binären Suchbaum dem Problemlöser bekannt sein (vgl. https://de.wikipedia.org/wiki/Bin%C3%A4rbaum#Traversierung ). Der Nachfolger entspricht also dem kleinsten Wert in dem Baum, der größer als der Wert des gegebenen Knotens ist
Details:
Wenn ein Knoten kein rechtes Kind hat, dann ist dessen Nachfolger dessen Elternknoten. Außer diesem ist der Nachfolger immer der Knoten mit dem kleinsten Wert in dem rechten Unterbaum, der linkeste Knoten dabei. Die Lösung kann dementsprechend rekursiv implementiert werden.
Solution and Further Explanation: https://github.com/spiralgo/algorithms/pull/181 Default Code:
Last updated