2015年9月10日星期四

Lintcode: Remove Node in Binary Search Tree

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.
Have you met this question in a real interview? 
Yes
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
Tags Expand 
LintCode Copyright Binary Search Tree




There are 3 cases when deleting a node:
1. the node is leaf node
2. the node has one child
3. the node has two children: in this code, we copy the minimum number of the right subtree or the max number of the left subtree, and then delete the duplicated node in corresponding subtree, if the duplicated node still has two children, repeat the above process recursively

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @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.
     */
    TreeNode* removeNode(TreeNode* root, int value) {
        // find the delete node 
        if(root == NULL) return NULL;
        if(root->val < value) root->right = removeNode(root->right, value);
        else if(root->val > value) root->left = removeNode(root->left, value);
        //got the node
        else{
            //0 child
            if(root->left == NULL && root->right == NULL){
                delete root;
                root = NULL;
            }
            //1 child
            else if(root->left == NULL){
                TreeNode* temp = root;
                root = root->right;
                delete temp;
            }
            else if(root->right == NULL){
                TreeNode* temp = root;
                root = root->left;
                delete temp;
            }
            //2 children
            else{
                int min = getMin(root->right);
                root->val = min;
                root->right = removeNode(root->right, min);
            }
        }
        return root;
    }
    int getMin(TreeNode* node){
        if(node->left) return getMin(node->left);
        else return node->val;
    }
};

Lintcode second:
Try reference pointer and succeed!
delete recursively without return value
find --- log(n)
delete -- O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @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.
     */
    TreeNode *removeNode(TreeNode* &root, int value){
        _removeNode(root, value);
        return root;
    }
    void _removeNode(TreeNode* &root, int value) {
        // write your code here
        if(root == NULL) return;
        if(value > root->val) removeNode(root->right, value);
        else if(value < root->val) removeNode(root->left, value);
        else if(value == root->val){
            if(root->left == NULL && root->right == NULL){
                delete root;
                root = NULL;
            }
            else if(root->left == NULL){
                TreeNode* temp = root->right;
                delete root;
                root = temp;
            }
            else if(root->right == NULL){
                TreeNode* temp = root->left;
                delete root;
                root = temp;
            }
            else{
                root->val = getMax(root->left);
                removeNode(root->left, root->val);
            }
        }
    }
    int getMax(TreeNode* root){
        if(root->right) getMax(root->right);
        else return root->val;
    }
};
发帖者 时间：
标签：

没有评论:

发表评论

订阅： 博文评论 (Atom)