Delete Node in a BST

Leave a comment

February 17, 2017 by oneOokay

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.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

删除搜索树中的一个点,返回新的搜索树的root.

  • 一种recursive: 调用自身
  • 一种iterative:需要另一个method: deleteRoot(TreeNode)来删除找到的node.

当删除的点同时存在左儿子和右儿子的时候,可以有两种处理方法:

  1. 把node替换成node的右儿子:此时需要把node的左儿子变成原node右儿子的最左儿子的左儿子
  2. 把node替换成node的左儿子:此时需要把node的右儿子变成原node左儿子的最右儿子的右儿子

技巧:引入一个dummy node,使得dummy.left = root,这样就可以处理root本身被delete的情况.

Iterative:
public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;
        TreeNode dummy = new TreeNode(-1);//引入dummy node
        dummy.left = root;
        TreeNode parent = dummy;
        TreeNode node = root;
        while (node != null && node.val != key){
            parent = node;
            if (node.val > key){
                node = node.left;
            }else {
                node = node.right;
            }
        }//找到要删除的node
        if (node == null) return null;
        if (parent.left == node){
            parent.left = deleteRoot2(node);
        }else{
            parent.right = deleteRoot2(node);
        }
        return dummy.left;
        
    }
    //左儿子作为新的root,所以要把右儿子变成左儿子的最右儿子
    private TreeNode deleteRoot2(TreeNode root){
        if (root == null) return null;
        if (root.left == null) return root.right;
//这里可以直接用root作为一个navigation node,不需要定义左右.
        TreeNode node = root.left;
        while (node.right != null){
            node = node.right;
        }
        node.right = root.right;
        return root.left;
    }
    
    //右儿子作为新的root,所以要把左儿子变成右儿子的最左儿子.
    private TreeNode deleteRoot(TreeNode root){
        if (root == null) return null;
        if (root.right == null) return root.left;
        //右儿子不是null,找到右儿子的最左儿子.
        TreeNode node = root.right;
        while (node.left != null){
            node = node.left;
        }
        node.left = root.left;
        return root.right;
    }
Recursive:
public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;
        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;
            if (root.right == null) return root.left;
            //把node替换为左儿子(方法2)
            TreeNode tmp = root.left;
            //找到左儿子的最右的叶子
            while (tmp.right != null) tmp = tmp.right;
            //把右儿子变成左儿子最右叶子的右儿子
            tmp.right = root.right;
            return root.left;//完成重构了,返回root的左儿子,此时root就被删掉了
            
            /* //把node替换为右儿子(方法1)
            TreeNode tmp = root.right;
            //找到root右儿子的最左儿子
            while (tmp.left != null) tmp = tmp.left; 
            tmp.left = root.left;
            return root.right;
            */
        }
        return root;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: