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.

BST删除key对应的节点之后还是要保持BST;

  1. 删除的节点没有right child: root直接指向left即可；
  2. vice versa;
  3. 都没有，不影响;
  4. 如果left, right child都有，并不是right child移动到root就行了: e.g. 
1
2
3
4
5
6
7
     7
    / \
   4   8
 /   \     --> 删除4, 补5，并不是6 
2     6
 \   /
  3 5
1
2
3
4
5
6
7
     7
    / \
   5   8   <-- 5: 也就是root节点中right child的子节点中最左边的节点
 /   \   
2     6  
 \   
  3

  1. Without BST; just BT. Recursive:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null) cur = cur.left;
                int tmp = root.val;
                root.val = cur.val;
                cur.val = tmp;
            }
        }
        
        root.left = deleteNode(root.left, key);
        root.right = deleteNode(root.right, key);
        return root;
    }

  2. BST的性质;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val > key) root.left = deleteNode(root.left, key);
        else if (root.val < key) root.right = deleteNode(root.right, key);
        // found the node to delete
        else {
            if (root.left == null || root.right == null) {
                root = (root.left != null) ? root.left : root.right;
            } else {
                TreeNode cur = root.right;
                while (cur.left != null) cur = cur.left;
                root.val = cur.val;
                root.right = deleteNode(root.right, key);
            }
        }
        return root;
    }

Achtung:

root.left, root.right=…, 可以理解成在左子树或者右子树中递归，来做这个递归函数要完成的事情

  1. root.val vs key: 找到要删除的节点；注意这里是root.left或者root.right的赋值，并不是return; 因为并不是直接返回结果，而是要继续找那个node
  2. 如果有子节点为空，直接指向另一个非空节点；如果都为空也满足；
  3. 子节点都不为空，右子树中找到最左下方的子节点和当前root交换；然后用deleteNode函数删除这个最左下方的节点，因为这个节点为了满足新生成的BST已经在root的位置了，所以自己本身要删掉