Today's sharing topics come from LeetCode No. 450: Delete nodes in the binary search tree. Although its difficulty is medium, it is actually very understanding, please see it down!
Topic description
Given the root node root and a value of the binary search tree, delete the node corresponding to the KEY in the binary search tree, and ensure that the nature of the binary search tree is constant. Returns a reference to the node of the binary search tree (possibly updated).
In general, deleting nodes can be divided into two steps:
First find the node that you need to delete;
If you find it, delete it.
Explanation: Requires algorithm time complexity of o (h), H is the height of the tree.
Example:
Root = [5, 3, 6, 2, 4, null, 7] Key = 3 5/36/247 The node value for the need to delete is 3, so we first find 3 this node and then delete it. A correct answer is [5, 4, 6, 2, NULL, NULL, 7], as shown below. 5/46/27 Another correct answer is [5, 2, 6, NULL, 4, NULL, 7]. 5/26 47
Topic analysis
Delete a node on the binary search tree, this topic has an implicit condition, that is, the value of the node on the tree is not repeated.
In addition, the title also requires time complexity to ensure that H here is the height of the binary tree.
In fact, this topic is divided into two steps, the first is to find the corresponding node, the second is to delete the node.
Because it is a binary search tree, for each node on the tree, the nodes of the right tree are greater than the node of their left sub-tree, then we must find the corresponding node, we can start from the root node, all the way, big Go to the right, you can find it on the left, so we all go down every time, you can guarantee that time complexity is O (H).
When we found the nodes to be deleted, there will be many details in deleting this step, mainly because we need to adjust the remaining structure to maintain the nature of the binary search tree.
For this problem, we can discuss the situation:
5/36/247/18
Situation 1: When the deleted node does not have left and right bonus, such as 4, 8, 1 above
At this time, you can delete it directly, the tree can still keep the nature of the binary search tree.
Situation 2: When the deleted node has a left sub-tree without a right tree, such as 2 above
At this time, we only need to move the entire left sub-tree to the current position.
That is, put the root node of the left sub-tree in the location of the deleted node, the rest remain
Situation 3: When the deleted node does not have the left subtree, there is a right sub-tree, such as 6, 7 above.
At this time, we only need to move the entire right child to the current position.
That is, put the root node of the right tree to the location of the deleted node, the rest remain
Situation 4: When the deleted node has both a left sub-tree, there is a right, such as 5, 3 above.
There are two ways to choose from:
Go to the left sub-tree, find the largest node of the value, move all the right people to this node
Go to the right sub-tree, find the smallest node, move the left sub-tree to this node
Through the discussion analysis above, we have a rough idea. In terms of implementation, we can use the return of the back to delete the purpose of deleting the corresponding nodes.
image description
Reference Code
// Five-minute 学 算 算 p {if (root == null) {if (root == null) {RETURNNULL;} // The node currently traversed is greater than the node you want to find, go to the left to continue find IF (root.val>key ) {root.left = deletenode (root.left, key);} // The node currently traversed is less than the node to be found, go to the right, continue to find Elseif (root.val< key) {root.right = deletenode Root.right, key);} / / Find the node you want to delete, delete operation else {// case 1 & 2 if (root.right == null) {return root.Left;} // case 3 IF (root {RETURN ROOT.right;} // Go to the right child of the delete node, find the smallest value of the value Treenode Rightsmallest = rootsmallest; = null) {Rightsmallest = Rightsmallest. Left;} // All left subtles of the delete node moved to this node RightsMallest.Left = root.Left; // Return the root node of the right child, put it in the current delete node Return root.right;} return Root;}, read full text, original title: five minutes to understand a medium difficult algorithm
Article Source: [Micro Signal: THEALGORITHM, WeChat public number: FPGA Development Circle] Welcome to add attention! Please indicate the source of the article.
Our other product:
