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.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

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 following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

time o(h) . space o(1)

1. 找到要删除的点，并且保留其父节点，并且知道是父节点的左或右

2. 调用删除方程，删除方程返回的点就是要放在被删除的点那里

3. 删除的话有这么几种情况，

   1. root没有左右节点，直接返回null

   2. root只有左节点，返回做节点

   3. root只有右节点，返回右节点（就算右节点后面还有子树，但是返回给要删node的父节点后，bst 结构不变）

   4. root左右节点都有，这种情况 要找到root右子树的最小值，如果root的右节点就是最小值，那么直接让右节点的left = root=left 返回，不然还是要有一个节点找到最小值，和最小值的上一个点，移动指针 取代root。

4. 坑：当要删的是第一个节点时，也要判断

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
        private TreeNode deleteRootNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode next = root.right;
        TreeNode pre = null;
        for(; next.left != null; pre = next, next = next.left);
        next.left = root.left;
        if(root.right != next) {
            pre.left = next.right;
            next.right = root.right;
        }
        return next;
    }
    public TreeNode deleteRoot(TreeNode root){
        if(root == null)
            return null;
        
        if(root.left == null)
            return root.right;
        
        if(root.right == null)
            return root.left;
        
        TreeNode next = root.right;
        
       
        TreeNode pre = null;
        
        while(next.left != null){
            pre = next;
            next = next.left;
        }
        next.left = root.left;
        
        if(next != root.right){
            pre.left = next.right;
        
            next.right = root.right;
        } 
        return next;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return null;
        
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null && cur.val != key){
            pre = cur;
            
            if(key < cur.val){
                cur = cur.left;
            }
            
            else if(key > cur.val){
                cur = cur.right;
            }
        }
        
        if(pre == null){
            return deleteRoot(cur);
        }
        
        else if(pre.left == cur){
            pre.left = deleteRoot(cur);
            
        }else{
            pre.right = deleteRoot(cur);
        }
        
        return root;
    }
    
    
    
    
    
}