Leetcode skimming: binary tree 27 (delete nodes in the binary search tree)

450. Delete nodes in binary search tree

Force button topic link

Given the root node of a binary search tree root And a value key, Delete the key Corresponding node , And keep the property of binary search tree unchanged . Back to binary search tree （ May be updated ） Reference to the root node of .

Generally speaking , Deleting a node can be divided into two steps ：

First find the node to be deleted ;
If you find it , Delete it .
explain ： The time complexity of the algorithm is required to be $O(h)$,h Is the height of the tree .

Example :

Ideas

The node deletion of the search tree is much more complicated than the node addition , There are many situations to consider , Be prepared .

This question is not difficult , It will be finished in five hours . I don't want to write an explanation . Careful simulation , Follow the picture more , Be sure to draw .

package com.programmercarl.tree;

import com.programmercarl.util.GenerateTreeNode;

/** * @ClassName DeleteNode * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 15:08 * @Version 1.0 * https://leetcode.cn/problems/delete-node-in-a-bst/ * 450.  Delete nodes in binary search tree  **/
public class DeleteNode {
    

    public static void main(String[] args) {
    
        System.out.println(new Traversal().inorderTraversal(
                new DeleteNode().deleteNode(GenerateTreeNode.generateTreeNode("[2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]"), 33)
        ));
    }


    public TreeNode deleteNode(TreeNode root, int key) {
    
        if (root == null) {
    
            // The node of the current value does not exist 
            return null;
        }
        if (root.val == key) {
    
            //  The parent node does not exist 
            if (root.left != null && root.right == null) {
    
                return root.left;
            }

            if (root.left == null && root.right != null) {
    
                return root.right;
            }
            // There is only one node 
            if (root.left == null && root.right == null) {
    
                return null;
            }
            // The rest is that both left and right nodes exist 
            TreeNode left = root.left;
            TreeNode right = root.right;
            if (root.right.left == null) {
    
                // If the left side of the right child node does not exist 
                //  Then the left side of the direct right child node is the left child node 
                root.right.left = left;
                // Return to header node   The right child node 
                return root.right;
            } else if (root.left.right == null) {
    
                // If the right side of the left child node does not exist 
                //  Then the right side of the direct left child node is the right child node 
                root.left.right = right;
                // Return to header node   The right child node 
                return root.left;
            } else {
    
                // If the left and right subtrees have their own left and right subtrees 
                // Let the rightmost sub node of the left sub tree replace root The value of the can 
                TreeNode leftRightNode = left.right;
                while (leftRightNode.right != null) {
    
                    left = left.right;
                    leftRightNode = leftRightNode.right;
                }
                // here leftRightNode It is the child node in the bottom right corner 
                int value = leftRightNode.val;
                // Delete the bottom right node 
                left.right = null;
                root.val = value;
                return root;
            }
        }
        TreeNode rootNode = root;
        parentNode = root;
        findNode(rootNode, key, false);
        return root;
    }

    TreeNode parentNode;

    public TreeNode findNode(TreeNode root, int key, boolean isLeft) {
    
        if (root == null) {
    
            // The node of the current value does not exist 
            return null;
        }
        if (root.val > key) {
    
            parentNode = root;
            findNode(root.left, key, true);
        } else if (root.val < key) {
    
            parentNode = root;
            findNode(root.right, key, false);
        } else {
    
            // Find value 
            // root.val == key
            // root  There may be old and young 
            //  The parent node   The left child node   The right child node 
            // If the parent node exists 
            if (root.left != null && root.right == null) {
    
                // The left node of the current node exists , The right node does not exist 
                // The current node is the left child node of the parent node , That is, the parent node is larger than the current node 
                if (isLeft) {
    
                    parentNode.left = root.left;
                } else {
    
                    //  If the current node is the right child node of the parent node , That is, the parent node is smaller than the current node 
                    parentNode.right = root.left;
                }
                return null;
            }

            if (root.left == null && root.right != null) {
    
                // The left node of the current node does not exist , The right node exists 
                // The current node is the left child node of the parent node , That is, the parent node is larger than the current node 
                if (isLeft) {
    
                    parentNode.left = root.right;
                } else {
    
                    //  If the current node is the right child node of the parent node , That is, the parent node is smaller than the current node 
                    parentNode.right = root.right;
                }
                return null;
            }

            if (root.left == null && root.right == null) {
    
                // If the current node is a leaf node 
                if (isLeft) {
    
                    parentNode.left = null;
                } else {
    
                    parentNode.right = null;
                }
                return null;
            }

            // Both left and right parent nodes exist 
            //  If the current node is the left node of the parent node 
            //  That is, the current node is smaller than the parent node 
            if (isLeft) {
    
                // If the left and right subtrees have their own left and right subtrees 
                // Find the element in the bottom left corner of the right subtree to replace yourself 
                if (root.left == null && root.right == null) {
    
                    parentNode.left = null;
                } else if (root.left == null && root.right != null) {
    
                    parentNode.left = root.right;
                } else {
    
                    // Left   Right   It's not empty. 
                    if (root.left.right == null) {
    
                        parentNode.left = root.left;
                        root.left.right = root.right;
                    } else {
    
                        // The lower right corner of the left subtree is not empty 
                        TreeNode left = root.left;
                        TreeNode leftRightNode = left.right;
                        while (leftRightNode.right != null) {
    
                            left = left.right;
                            leftRightNode = leftRightNode.right;
                        }
                        int value = leftRightNode.val;
                        if (leftRightNode.left != null) {
    
                            left.right = leftRightNode.left;
                        } else {
    
                            left.right = null;
                        }
                        root.val = value;
                        return root;
                    }
                }
                return root;
            } else {
    
                // If the left and right subtrees have their own left and right subtrees 
                // Find the element in the bottom right corner of the left subtree to replace yourself 
                if (root.left == null && root.right == null) {
    
                    parentNode.right = null;
                } else if (root.right == null && root.left != null) {
    
                    parentNode.right = root.left;
                } else {
    
                    // Left   Right   It's not empty. 
                    if (root.right.left == null) {
    
                        parentNode.right = root.right;
                        root.right.left = root.left;
                    } else {
    
                        // The lower left corner of the right subtree is not empty 
                        TreeNode right = root.right;
                        TreeNode rightRightNode = right.left;
                        while (rightRightNode.left != null) {
    
                            right = right.left;
                            rightRightNode = rightRightNode.left;
                        }
                        int value = rightRightNode.val;
                        if (rightRightNode.right != null) {
    
                            right.left = rightRightNode.right;
                        } else {
    
                            right.left = null;
                        }
                        root.val = value;
                        return root;
                    }
                }
                return root;
            }
        }
        return null;
    }
}