450. Delete nodes in the binary search tree

“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Difficulty: MID Source: LeetCode

Topic content:

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).

In general, node deletion can be divided into two steps:

First find the node to delete; If found, delete it.

Example 1:

Input: root = [5,3,6,2,4, null, 7], the key = 3 output: [7] 5,4,6,2, null, null,

Explanation: Given that the value of the node to be deleted is 3, we first find the node 3 and then delete it. A correct answer is [5,4,6,2,null,null,7], as shown below. Another correct answer is [5,2,6,null,4,null,7].

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 output: [5,3,6,2,4,null,7]

Input: root = [], key = 0

-105 <= node. val <= 105 Node value Root is a valid binary search tree -105 <= key <= 105

Ideas:

The tree in the title is a binary search tree, where the property is:

  1. All values in the left subtree are less than the root node
  2. All values of the right subtree are greater than the root node
  3. The result of middle order traversal is increasing sequence
  4. Its left and right subtrees are also binary sort trees respectively

Root. val > key traverses the left subtree and root.val < key traverses the right subtree.

if(root.val < key) root.right = deleteNode(root.right,key);
else if(root.val > key) root.left= deleteNode(root.left,key);
Copy the code

When root.val == key, the value of the node to be deleted is found.

Here are four cases to consider:

  1. Delete the case where the left and right subtrees of the node do not exist (leaf node)

    Delete node directly — return NULL

    if(root.left == null && root.right == null) return null;
Copy the code

  2. Delete the case that the left subtree of the node does not exist

    Return directly to the right subtree

    if(root.left == null && root.right ! = null) return root.right;Copy the code

  3. Delete the case that the right subtree of the node does not exist

    if(root.left ! = null && root.right == null) return root.left;Copy the code

  4. If both the left and right subtrees of the deleted node exist

    This situation is a bit troublesome

    TreeNode temp = root.right; TreeNode temp = root.right; while(temp.left ! = null){ temp = temp.left; } root.val = temp.val; root.right = deleteNode(root.right,temp.val);Copy the code

    Deleting a node:

Complete code:

class Solution { public TreeNode deleteNode(TreeNode root, int key) { root = delete(root,key); return root; } TreeNode delete(TreeNode root,int key){ if(root == null) return null; If (root.val == key){// Both the left and right subtrees of the target node are empty if(root.left == null && root.right == null) return null; else if(root.left == null && root.right ! = null) return root.right; else if(root.left ! = null && root.right == null) return root.left; TreeNode temp = root.right; else{// The left and right subtrees are not empty. While (temp. Left! = null){ temp = temp.left; } root.val = temp.val; root.right = deleteNode(root.right,temp.val); } } if(root.val < key) root.right = deleteNode(root.right,key); else if(root.val > key) root.left= deleteNode(root.left,key); return root; }}Copy the code