代码随想录算法训练营第二十一天|450.删除二叉搜索树中的节点

450.删除二叉搜索树中的节点

private void swapValue(TreeNode a, TreeNode b) {
    int t = a.val;
    a.val = b.val;
    b.val = t;
}

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        //case 4.case4又分为4种小情况，最后一种可以被合并掉。
        //所以这里只处理了三种。
        // 当前树只有一个结点，那么直接返回null
        if (root.left == null && root.right == null) {
            return null;
        } else if (root.left != null) {
            // 当前结点还有左子树
            // 那么需要从左子树中找个较大的值。
            TreeNode large = root.left;
            while (large.right != null) {
                large = large.right;
            }
            //交换再删除
            swapValue(root, large);
            root.left = deleteNode(root.left, key);
        } else if (root.right != null) {
            // 当前结点还有右子树
            TreeNode small = root.right;
            //那么需要从右子树中找个较小的值
            while (small.left != null) {
                small = small.left;
            }
            //交换再删除
            swapValue(root, small);
            root.right = deleteNode(root.right, key);
        }


    }
    return root;
}