首页 > 代码库 > 【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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。