450 Delete Node in a BST

Leetcode

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:

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

Example 1:

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.

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: []

---

思路：找到要删除的节点的上一个节点，如果要删除的节点只有最多一个字节点，把字节点连到上一个节点。如果有两个子节点，把右子节点连到左子节点的最右边，再把左子节点连到上一个节点。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        if(root.val==key){
            if(root.left==null) return root.right;
            else if (root.right==null) return root.left;
            else {
                TreeNode r=rightest(root.left);
                r.right=root.right;
                return root.left;
            }
        } 
        TreeNode pre = search(root, key);
        if(pre==null) return root;
        TreeNode toDel=null;
        if(pre.val<key){
            toDel=pre.right;
            if(toDel.left==null) {
                pre.right=toDel.right;
                return root;
            } else if(toDel.right==null){
                pre.right=toDel.left;
                return root;
            }
            TreeNode rightest=rightest(toDel.left);
            pre.right=toDel.left;
            rightest.right=toDel.right;
            return root;
            
        } else {
            toDel=pre.left;
            if(toDel.left==null) {
                pre.left=toDel.right;
                return root;
            } else if(toDel.right==null){
                pre.left=toDel.left;
                return root;
            }
            TreeNode rightest=rightest(toDel.left);
            pre.left=toDel.left;
            rightest.right=toDel.right;
            return root;
        }
        
    }
    
    private TreeNode search(TreeNode root, int key){
        if(root==null) return null;
        if(root.val<key){
            if(root.right!=null && root.right.val==key) return root;
            return search(root.right, key);
        } else{
            if(root.left!=null && root.left.val==key) return root;
            return search(root.left, key);
        } 
    }
    
    private TreeNode rightest(TreeNode root){
        while(root.right!=null) root=root.right;
        return root;
    }
}