给定一棵具有不同节点值的二叉查找树,删除树中与给定值相同的节点。如果树中没有相同值的节点,就不做任何处理。你应该保证处理之后的树仍是二叉查找树。
样例
给出如下二叉查找树:
删除节点3之后,你可以返回: 或者:标签
二叉查找树 LintCode 版权所有
思路
若要删除一个BST的一个结点,需要考虑如下三种情况:
- 需要删除的节点下并没有其他子节点
- 需要删除的节点下有一个子节点(左或右)
- 需要删除的节点下有两个子节点(既左右节点都存在)
对这三种情况分别采取的措施是:
- 直接删除此结点
- 删除此结点,将此结点父节点连接到此结点左(右)子树
- 找出此结点右子树中的最小结点,用以代替要删除的结点,然后删除此最小结点
code
/** * 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 == NULL) { return NULL; } if(root->val > value) { root->left = removeNode(root->left, value); } else if(root->val < value) { root->right = removeNode(root->right, value); } else { if (root->left == NULL || root->right == NULL) { root = (root->left != NULL) ? root->left : root->right; } else { TreeNode *cur = root->right; while (cur->left != NULL) { cur = cur->left; } root->val = cur->val; root->right = removeNode(root->right, cur->val); } } return root; }};