Fetch the repository succeeded.
/*
@Copyright:LintCode
@Author: tjyemail
@Problem: http://www.lintcode.com/problem/remove-node-in-binary-search-tree
@Language: C++
@Datetime: 17-03-23 11:16
*/
/**
* 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.
* See http://eudiwffe.cnblogs.com/p/6207196.html for details
* Erase node from a bst - sketch, i' is special for erase 6 (i)
* 6 d=6,(3) f=6 6 d=6,(5)
* / \ / \ / \ / \ / \
* / \ / \ / \ / \ / \
* 3 8 p=3 8 d=3 8 3 f=8 f=3 8
* / / \ / / \ / / \ / / \ / \ / \
* / / \ / / \ / / \ / / \ / \ / \
* 2 7 9 2 7 9 2 7 9 2 d=7 9 2 p=5 7 9
* /
* BST (i) (ii) (iii) / (i')
* erase 6 erase 3 erase 7 4
*/
TreeNode* removeNode(TreeNode* root, int val) {
// write your code here
TreeNode *f, *p, *d;
// f is father node
// p is precursor node
// d is to be deleted node
for (f=NULL,d=root; d && d->val!=val;){
f = d;
if (d->val < val) d=d->right;
else d=d->left;
}
if (d==NULL) return root; // cannot find erase node
if (d->left && d->right){ // deletion has two children
// find deletion node d's precursor
for (f=d,p=d->left; p->right; f=p, p=p->right);
d->val = p->val; // replace deletion val by precursor
if (f==d) d->left = p->left;// case (i)
else f->right = p->left; // case (i')
}
else if (d->left==NULL && d->right==NULL){
if (d==root) {
delete root;
return NULL; // deletion is single root
}
// deletion is leaf
if (f->left == d) f->left=NULL;
else if (f->right == d) f->right=NULL;
delete d;
}
else { // deletion has single child node or branch
p = (d->left ? d->left : d->right);
d->val = p->val;
d->left = p->left;
d->right = p->right;
delete p;
}
return root; // return erase node count
}
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。