/**
1. 按目标点有无子树划分为4中情况:
2.1 : 无子树:  直接删掉
2.2 : 无左子树: 把右子树接到父节点上, 特判下根节点
2.3 : 无右子树: 把左子树接到父节点上, 特判下根节点,  (2,3可合并)
2.4 : 都有:  左子树的最右叶子节点 和 右子树的最左叶子节点 中任意一个swap到target节点后delete掉
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode[] targets = search(root, key);
        if (targets == null || root == null) return root;
        TreeNode prev = targets[0];
        TreeNode cur = targets[1];

        if (cur.right == null || cur.left == null){
            if (prev == cur) return  cur.right == null ? cur.left : cur.right ;
            delete(prev, cur);
        } else if (cur.left != null && cur.right != null){
            TreeNode candidates[] = getMostLeft(cur.right);
            TreeNode candidate = candidates[1];
            TreeNode father = (candidates[0] == candidate ? cur : candidates[0]);
            // TreeNode father = candidates[0];
            cur.val = candidate.val;
            delete(father, candidate);
        }
        return root;
    }

    private void delete(TreeNode prev, TreeNode cur){
        if (prev.left == cur){
            if (cur.left != null) prev.left = cur.left;
            else prev.left = cur.right;
        } else if (prev.right == cur){
            if (cur.left != null) prev.right = cur.left;
            else prev.right = cur.right;
        }
    }

    private TreeNode[] getMostLeft(TreeNode root){
        TreeNode prev = root, cur = root;
        while(cur.left != null) {
            prev = cur;
            cur = cur.left;
        }
        TreeNode[] res = {prev, cur};
        return res;
    }

    private TreeNode[] search(TreeNode root, int key){
        TreeNode prev = root, cur = root;
        while (cur != null ){
            if (cur.val == key){
                TreeNode[] res = {prev, cur};
                return res;
            } else if (cur.val < key){
                prev = cur;
                cur = cur.right;
            } else {
                prev = cur;
                cur = cur.left;
            }
        }
        return null;
    }
}