Remove Node in Binary Search Tree 87

Question

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

5

/ \ 3 6 / \ 2 4

Remove 3, you can either return:

5

/ \ 2 6 \ 4

or

5

/ \ 4 6 / 2

Solution

首先在bst中搜索node值为value的点及其父节点。

下一步将该点从bst中删除。

1) 若要删除节点的右子树为空，则直接将要删除节点的左子树与其父节点连接。

2) 若要删除节点的右子树不为空，则要找到右子树的最小值（右子树的最左边节点）使其成为以要删去节点为根节点的子树的新的根节点。

3) 首先将右子树最小值节点的右子树与右子树最小值节点的父节点连接（即从右子树中删去最小值节点，最小值节点在之前被保存），然后将要删去节点的父节点与最小值节点连接，最后将要删去节点的左右子树分别与最小值节点连接。

代码如下：

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        // write your code here
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;

        TreeNode parent = findNode(dummy, root, value);
        TreeNode node;
        if(parent.left != null && parent.left.val == value){
            node = parent.left;
        }else if(parent.right != null && parent.right.val == value){
            node = parent.right;
        }else{
            //没找到
            return dummy.left;
        }

        deleteNode(parent, node);
        return dummy.left;
    }

    private TreeNode findNode(TreeNode parent, TreeNode node, int value){
        if(node == null){
            return parent;
        }

        if(node.val == value){
            return parent;
        }

        if(value < node.val){
            return findNode(node, node.left, value);
        }else{
            return findNode(node, node.right, value);
        }
    }

    private void deleteNode(TreeNode parent, TreeNode node){
        if(node.right == null){
            if(parent.left == node){
                parent.left = node.left;
            }else{
                parent.right = node.left;
            }
        }else{
            TreeNode temp = node.right;
            TreeNode father = node;

            while(temp.left != null){
                father = temp;
                temp = temp.left;
            }

            if(father.left == temp){
                father.left = temp.right;
            }else{
                father.right = temp.right;
            }

            if(parent.left == node){
                parent.left = temp;
            }else{
                parent.right = temp;
            }

            temp.left = node.left;
            temp.right = node.right;
        }
    }
}