首页 > 代码库 > 【Lintcode】087.Remove Node in Binary Search Tree

【Lintcode】087.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.

Given binary search tree:

    5
   /   3   6
 / 2   4

Remove 3, you can either return:

    5
   /   2   6
       4

or

    5
   /   4   6
 /
2

 

题解:

  这个题就是考察对二叉树操作的熟练程度,没有多少技巧,下面的程序中唯一能算作技巧的是更换node时有时并不需要切断其与左右节点和父节点的链接,只需要更换val值就可以了。

Solution 1 ()

class Solution {
public:
    TreeNode* removeNode(TreeNode* root, int value) {
        if (root == NULL)
            return NULL;
        TreeNode * head = new TreeNode();
        head->left = root;
        TreeNode * tmp = root, *father = head;

        while (tmp != NULL) {
            if (tmp->val == value)
                break;
            father = tmp;
            if (tmp->val > value)
                tmp = tmp->left;
            else
                tmp = tmp->right;
        }
        if (tmp == NULL)
            return head->left;

        if (tmp->right == NULL) {
            if (father->left == tmp)
                father->left = tmp->left;
            else
                father->right = tmp->left;
        } else 
        if (tmp->right->left == NULL) {
            if (father->left == tmp)
                father->left = tmp->right;
            else
                father->right = tmp->right;

            tmp->right->left = tmp->left;
            
        } else {
            father = tmp->right;
            TreeNode * cur = tmp->right->left;
            while (cur->left != NULL) {
                father = cur;
                cur = cur->left;
            }
            tmp->val = cur->val;
            father->left = cur->right;
        }
        return head->left;
    }
};

 

【Lintcode】087.Remove Node in Binary Search Tree