preface

Today, I reviewed the deletion operation of binary search tree, and found that I could not write buffree code at the same time. It was a little strange, and I was recording one.

The title

Delete a node in the binary search tree

Given the root node of a binary search tree root and a value of key, delete the nodes corresponding to key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated). Generally speaking, node deletion can be divided into two steps: first, find the node to be deleted; If found, delete it. Note: The algorithm time complexity is O(h), h is the height of the tree.Copy the code

The title and dismantling

This question is also a basic skills topic, testing the properties of binary search tree and the basic operation of the master degree, so, not five minutes to write bugfree code, is the basic skills are not solid… To reflect on…

Without further ado, why don’t we review what binary search trees are and their properties

  • Binary search tree is a binary tree with a sort relationship
  • The value of the left node of each node is smaller than the value of the current node, and the value of the right node of each node is larger than the value of the current node
  • The middle-order traversal of a binary search tree results in an ordered array

Delete a node. Delete a node. Delete a node. So, in two steps,

  • To find the node
  • Remove nodes

To find the node

  • If the target value is smaller than the current node value, search to the left according to the binary search tree property.
  • If the target value is larger than the current node value, search to the right according to the binary search tree property.
  • If the current node value is equal to the target value, the deletion operation is performed.

Remove nodes

Here we also consider the case of the targeted node, divided into these types

  • The node to be deleted is the leaf node, do not hesitate to delete directly
  • The left subtree of the node to be deleted is not empty. Replace the current node with a precursor node.
  • The right subtree of the node to be deleted is not empty. Replace the current node with a successor node.

There’s another way of thinking about it,

  • The node to be deleted is the leaf node, do not hesitate to delete directly
  • One of the left and right subtrees is empty, and the current node is replaced with a non-empty child node.
  • The left and right subtrees are not empty, and the precursor node or subsequent node replaces the current node.

The second way is to write the code with the parent node in the recursion, otherwise there is no way to directly replace the child node with the current node, so I’ll do the first way today.

Here said the two concepts, precursor and subsequent nodes, but also is easy to understand, it says in the nature of a binary search tree is in the sequence traversal is ordered, so is the precursor of a node in the sequence traversal results, in front of the node, the node in the same way, in the sequence traversal in next to the next node of the current node, is the subsequent nodes.

One more thing, in a binary search tree, the forerunner of a node is the right-most node of the left subtree, and the largest node of the left subtree, and that’s where that forerunner is in the middle order traversal. The same goes for the successors.

Now, let’s go straight to the code

code

Class Solution {public TreeNode deleteNode(TreeNode root, int val) {if (root == null) {return null; } if (root.left == null && root.right == null) {root = null; } else if (root.right ! Val = findMinNode(root).val; root.right = deleteNode(root.right, root.val); } else {// If the left subtree is not empty, find the precursor node and replace root.val = findMaxNode(root).val; root.left = deleteNode(root.left, root.val); }} else if (val < root.val) {root.left = deleteNode(root.left, val); } else {root.right = deleteNode(root.right, val); } return root; } TreeNode findMaxNode(TreeNode root) {// Find the maximum value, go to the left, then go all the way to the right. while (res.right ! = null) { res = res.right; } return res; } TreeNode findMinNode(TreeNode root) {// Find the minimum value, go one step to the right, then go all the way to the left to end TreeNode res = root.right; while (res.left ! = null) { res = res.left; } return res; }}Copy the code

conclusion

Basic skills or to master, binary tree basic add, delete, change and check, binary search element tree add, delete, change and check, find the precursor, find the successor, solid basic skills, in order to solve the problem more quickly.

This article is participating in the “Nuggets 2021 Spring recruiting campaign. Click here to view