LintCode (87) 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

基础题，和那个插入node一个思路， 如果小于当前， 插入（删除）左面， 如果大于当前， 插入（删除）右面。如果（NULL)相等，插入删除当前。

在处理当前项的时候有这三种情况：

1. 无左孩子，那么返回右孩子并删除当前

2. 无右孩子，返回左孩子并删除当前

3. 都有， 交换当前与右孩子的最小值 （leaf），并从右子数中删除当前值

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

/** * 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) { // write your code here if (!root) return 0; if (value<root->val) root->left=removeNode(root->left, value); else if (value>root->val) root->right=removeNode(root->right, value); else{ if (!root->right){ TreeNode* tmp=root->left; delete root; return tmp; } if (!root->left){ TreeNode* tmp=root->right; delete root; return tmp; } TreeNode* tmp=root->right; while(tmp->left) tmp=tmp->left; swap(root->val, tmp->val); root->right=removeNode(root->right, tmp->val); } return root; } };