You are given a binary search tree (BST) and a number key. Delete the node that holds key from the tree, and return the tree after the deletion. If no node holds key, the tree stays as it is.
The work has two steps: find the node, then remove it.
Which tree to return: more than one tree can be right, but the judge compares your answer with one fixed tree. Use these rules. A node with no children is simply removed. A node with one child is replaced by that child. A node with two children takes the value of its in-order successor (the smallest value in its right subtree), and then that successor node is deleted from the right subtree.
How the judge passes the data
Examples
Example 1:
Input: root = [8,4,12,2,6,10,14], key = 4
Output: [8,6,12,2,null,10,14]
Explanation: The node 4 has two children. Its successor is 6, the smallest value on its right. 6 takes the place of 4, and the old node 6 is removed.
Example 2:
Input: root = [5,3,6,null,4], key = 3
Output: [5,4,6]
Explanation: The node 3 has only one child, 4. The child takes its place.
Example 3:
Input: root = [8,4,12,2,6,10,14], key = 99
Output: [8,4,12,2,6,10,14]
Explanation: No node holds 99, so the tree does not change.