LeetCode - Medium - 450. Delete Node in a BST

港控/mmm° 2022-10-05 13:48 119阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/delete-node-in-a-bst/][https_leetcode.com_problems_delete-node-in-a-bst]

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1.  Search for a node to remove.
2.  If the node is found, delete the node.

**Follow up:** Can you solve it with time complexity `O(height of tree)`?

**Example 1:**

![05c3cafc93516b86ed20c6525b23184c.png][]

Input: root = [5,3,6,2,4,null,7], key = 3
    Output: [5,4,6,2,null,null,7]
    Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
    One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
    Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

![91180740562b7a82bd0d594a2a82c5c2.png][]

**Example 2:**

Input: root = [5,3,6,2,4,null,7], key = 0
    Output: [5,3,6,2,4,null,7]
    Explanation: The tree does not contain a node with value = 0.

**Example 3:**

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

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\].
 *   − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105
 *  Each node has a **unique** value.
 *  `root` is a valid binary search tree.
 *   − 1 0 5 < = k e y < = 1 0 5 -10^5 <= key <= 10^5 −105<=key<=105

## Analysis ##

方法一：我写的。

1.  找出目标节点，找到即返回它和它的父节点，找不到直接结束算法。
2.  如果目标节点是根节点，就给它弄个临时父节点，原根节点成为它的左子树。
3.  根据目标节点的左右子树的有无指定删除方案：
    
     *  目标节点是叶子节点，或只有一个左子树，或只有一个右子树，则采用类似单链表删除节点方法（这就需要用到目标节点的父节点）。
     *  目标节点都有左右子树，则从右子树中查找出最小值节点，让它值替换目标节点值，随后在右子树移除最小值节点。由于BST的性质，最小值节点有么是叶子节点，有么只有右子树，只有这两种情况，则放心采用类似单链表删除节点方法移除最小值节点。
4.  最后，返回根节点。如果目标节点是根节点，则返回临时父节点的左子树。

方法二：别人写的，递归版，精简优雅。

> 1.  Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree.
> 2.  Once the node is found, have to handle the below 4 cases:
>     
>      *  node doesn’t have left or right - return null
>      *  node only has left subtree- return the left subtree
>      *  node only has right subtree- return the right subtree
>      *  node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then  
>         recursively delete the minimum value in the right subtree  
>         [link][]

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class DeleteNodeInABST { 
    	
    	//方法一：我写的
        public TreeNode deleteNode(TreeNode root, int key) { 
        	
        	TreeNode[] result = find(root, key);
        	
        	if(result != null) { 
    
        		TreeNode parent = result[0], target = result[1];
        		TreeNode fakeRoot = null;
        		
        		if(parent == null) { //删除根节点，弄个假根节点，原
        			fakeRoot = new TreeNode(Integer.MAX_VALUE, root, null);
        		}
        		
    			if(target.left != null && target.right != null) { //既有左子树，有右子树
    				TreeNode replaceOne = findReplaceOneFromRight(target, target.right);
    				target.val = replaceOne.val;
    			}else { 
    				removeEasyOne(parent == null ? fakeRoot: parent, target);
    			}
    		
        		if(parent == null) { //删除根节点的情况
        			root = fakeRoot.left;
        			fakeRoot.left = null;
        		}
        	}
        	
            return root;
        }
        
        private TreeNode[] find(TreeNode root, int key) {     	
        	TreeNode last = null, curr = root;
        	
        	while(curr != null) { 
        		
        		if(key < curr.val) { 
        			last = curr;
        			curr = curr.left;
        		}else if(curr.val < key){ 
        			last = curr;
        			curr = curr.right;
        		}else { 
        			return new TreeNode[] { last, curr};
        		}
        	}
    
        	return null;
        }
        
        /** * * target是叶子节点，target只有左子树，target只有右子数，这三种情况可以用链表式方法的删除节点 * */
        private void removeEasyOne(TreeNode parent, TreeNode target) { 
    		if(target.left == null && target.right == null) { //target是叶子节点
    			if(parent.left == target){ 
    				parent.left = null;
    			}else { 
    				parent.right = null;
    			}
    		}else if(target.left != null && target.right == null){ //target只有左子树
    			if(parent.left == target){ 
    				parent.left = target.left;
    				target.left = null;
    			}else { 
    				parent.right = target.left;
    				target.left = null;
    			}
    			
    		}else if(target.left == null && target.right != null){ //target只有右子数
    			if(parent.left == target){ 
    				parent.left = target.right;
    				target.right = null;
    			}else { 
    				parent.right = target.right;
    				target.right = null;
    			}
    		}
        }
        
        //查找右子树的最小值
        private TreeNode findReplaceOneFromRight(TreeNode last, TreeNode child) { 
        	if(child == null) return null;
        	
        	while(child.left != null) { //
        		last = child;
        		child = child.left;
        	}
        	removeEasyOne(last, child);
        	return child;
        }
    
        //方法二：别人写的，递归版，精简优雅了许多
        public TreeNode deleteNode2(TreeNode root, int key) { 
            if(root == null){ 
                return null;
            }
            if(key < root.val){ 
                root.left = deleteNode2(root.left, key);
            }else if(key > root.val){ 
                root.right = deleteNode2(root.right, key);
            }else{ 
                if(root.left == null){ 
                    return root.right;
                }else if(root.right == null){ 
                    return root.left;
                }
                
                TreeNode minNode = findMin(root.right);
                root.val = minNode.val;
                root.right = deleteNode2(root.right, root.val);
            }
            return root;
        }
    
        private TreeNode findMin(TreeNode node){ 
            while(node.left != null){ 
                node = node.left;
            }
            return node;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class DeleteNodeInABSTTest { 
    
    	@Test
    	public void test() { 
    		DeleteNodeInABST obj = new DeleteNodeInABST();
    
    		TreeNode root1 = obj.deleteNode(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 3);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(5,4,6,2,null,null,7);
    		assertTrue(BinaryTree.equals(root1, expected1));
    		
    		TreeNode root2 = obj.deleteNode(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 0);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7);
    		assertTrue(BinaryTree.equals(root2, expected2));
    		
    		assertNull(obj.deleteNode(null, 0));
    		
    		//删除根节点
    		TreeNode root3 = obj.deleteNode(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 5);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(6,3,7,2,4);
    		assertTrue(BinaryTree.equals(root3, expected3));
    		
    		assertNull(obj.deleteNode(new TreeNode(0), 0));
    	}
    	
    	@Test
    	public void test2() { 
    		DeleteNodeInABST obj = new DeleteNodeInABST();
    		
    		TreeNode root1 = obj.deleteNode2(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 3);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(5,4,6,2,null,null,7);
    		assertTrue(BinaryTree.equals(root1, expected1));
    		
    		TreeNode root2 = obj.deleteNode2(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 0);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7);
    		assertTrue(BinaryTree.equals(root2, expected2));
    		
    		assertNull(obj.deleteNode2(null, 0));
    		
    		//删除根节点
    		TreeNode root3 = obj.deleteNode2(BinaryTree.integers2BinaryTree(5,3,6,2,4,null,7), 5);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(6,3,7,2,4);
    		assertTrue(BinaryTree.equals(root3, expected3));
    		
    		assertNull(obj.deleteNode2(new TreeNode(0), 0));
    	}
    }

[https_leetcode.com_problems_delete-node-in-a-bst]: https://leetcode.com/problems/delete-node-in-a-bst/
[05c3cafc93516b86ed20c6525b23184c.png]: /images/20221005/0381002de7314162aa49dea65eb09b5c.png
[91180740562b7a82bd0d594a2a82c5c2.png]: /images/20221005/edf9dae4db1b433397d899b4d48e3394.png
[link]: https://leetcode.com/problems/delete-node-in-a-bst/discuss/93296/Recursive-Easy-to-Understand-Java-Solution