Thinking process

1. find the node
2. if left subtree doesn't exist, return the right child
3. if right child, return the left child;
4. if the node has two children, then set the node's value to the minimum value in its right subtree and then delete that minimum value.

public class Solution {
    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);
        else {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;

            root.val = getMinOfRight(root.right);
            root.right = deleteNode(root.right, root.val);
        }

        return root;
    }

    private int getMinOfRight(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }

        return root.val;
    }
}