Force deduction solution summary 450- delete nodes in the binary search tree

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

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 .
 

Example 1:

Input ：root = [5,3,6,2,4,null,7], key = 3
Output ：[5,4,6,2,null,null,7]
explain ： Given the node value to be deleted is 3, So first we found 3 This node , Then delete it .
The right answer is [5,4,6,2,null,null,7], As shown in the figure below .
The other 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]
explain : Binary tree does not contain a value of 0 The node of
Example 3:

Input : root = [], key = 0
Output : []
 

Tips :

Range of nodes  [0, 104].
-105 <= Node.val <= 105
Unique node value
root  Is a legitimate binary search tree
-105 <= key <= 105
 

Advanced ： The time complexity of the algorithm is required to be  O(h),h Is the height of the tree .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/delete-node-in-a-bst
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  First of all, the simplest way must be to convert a binary tree into a queue , Then reorder it . This must be the case , But the time complexity is high , Nor is it the point of this topic .
*  First, according to the properties of binary tree , find key Corresponding node , Then find the node , The leftmost node of the child nodes on the right replaces the current node . Then find the target node , We still have to parent Get rid of references to it .

Code ：

public class Solution450 {

    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode recursion = recursion(root, key);
        return recursion;
    }


    private TreeNode recursion(TreeNode current, int key) {
        if (current == null) {
            return null;
        }
        if (current.val == key) {
            if (current.right != null) {
                TreeNode left = current.left;
                TreeNode right = current.right;
                TreeNode node = findNode(current, current.right);
                node.left = left;
                if (node != right) {
                    node.right = right;
                }
                return node;
            }
            return current.left;
        }
        if (current.val > key) {
            current.left = recursion(current.left, key);
        } else {
            current.right = recursion(current.right, key);
        }
        return current;
    }

    private TreeNode findNode(TreeNode parent, TreeNode treeNode) {
        if (treeNode.left != null) {
            return findNode(treeNode, treeNode.left);
        }
        if (treeNode.right != null) {
            parent.left = treeNode.right;
        } else {
            parent.left = null;
        }
        return treeNode;
    }

}