Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/description/

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.

Thoughts

根据例子观察到可以用被删结点的右子树中的最左结点替代被删结点。因此需要1. 找到要删除的结点 2. 找到它的右子树的最左结点。

衍生出许多corner cases需要考虑，比如找不到目标结点怎么办，目标结点在root时和目标结点没有右子树怎么办。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode[] leftMost(TreeNode node, TreeNode par) {
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            return leftMost(node.left, node);
        }
        TreeNode[] res = new TreeNode[2];
        res[0] = node;
        res[1] = par;
        return res;
    }

    private TreeNode[] findNode(TreeNode node, int key, TreeNode par) {
        if (node == null) {
            return null;
        }

        if (node.val > key) {
            return findNode(node.left, key, node);
        } else if (node.val < key) {
            return findNode(node.right, key, node);
        } else {
            TreeNode[] res = new TreeNode[2];
            res[0] = node;
            res[1] = par;
            return res;
        }
    }


    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode[] result = leftMost(root.right, null);
                if (result[1] != null) {
                    result[1].left = result[0].right;
                }
                result[0].left = root.left;
                if (root.right != result[0]) result[0].right = root.right;
                return result[0];
            }
        }
        TreeNode[] res = findNode(root, key, null);
        if (res == null) {
            return root;
        }
        TreeNode target = res[0];
        TreeNode par = res[1];
        if (target == par.left) {
            if (target.left == null) {
                par.left = target.right;
            } else if (target.right == null) {
                par.left = target.left;
            } else {
                TreeNode[] result = leftMost(target.right, null);
                System.out.println(result[0].val );
                par.left = result[0];
                if (result[1] != null) {
                    result[1].left = result[0].right;
                }
                result[0].left = target.left;
                if (target.right != result[0]) result[0].right = target.right;              
            }
        } else {
            if (target.left == null) {
                par.right = target.right;
            } else if (target.right == null) {
                par.right = target.left;
            } else {
                TreeNode[] result = leftMost(target.right, null);
                par.right = result[0];
                if (result[1] != null) {
                    result[1].left = result[0].right;
                }
                result[0].left = target.left;
                if (target.right != result[0]) result[0].right = target.right;
            }
        }

        return root;
    }
}

Analysis

Errors:

1. 找不到目标结点时

2. if (target.right != result[0]) result[0].right = target.right; 没有加条件，导致形成环。

时间复杂度为一条路径长度O(h).

Ver.2

分三种情况讨论:

1. 目标点是null, 返回

2. 目标点在左/右树, 返回左/右树结果

3. 目标点在当前点, 从右子树中找到最左值放到该节点; 递归对右节点删除当前该点值的结点.

/**
 * 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) {
        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 {
            if(root.left == null){
                return root.right;
            } else if(root.right == null){
                return root.left;
            }

            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
}

Ver 3

Iterative版本的. 思路是一致的, 找到要被删的节点, 把它右子树中最小的换过来. 需要注意的是右子树中最小的它可能还有右子树, 不要忘了.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode rmRoot(TreeNode root) {
        if (root.right == null) {
            return root.left;
        } else if (root.left == null) {
            return root.right;
        } else {
            TreeNode min = root.right;
            TreeNode pre = root;
            while (min.left != null) {
                pre = min;
                min = min.left;
            }

            min.left = root.left;
            if (min != root.right) {
                pre.left = min.right;
                min.right = root.right;
            }
            return min;
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode pre = null, node = root;
        while (node != null) {
            if (key < node.val) {
                pre = node;
                node = node.left;
            } else if (key > node.val) {
                pre = node;
                node = node.right;
            } else {
                break;
            }
        }

        if (node == null || node.val != key) {
            return root;
        }

        if (pre == null) {
            return rmRoot(root);
        } else if (pre.left == node) {
            pre.left = rmRoot(pre.left);
        } else {
            pre.right = rmRoot(pre.right);
        }

        return root;
    }
}