a*n
2 楼
void RemoveFromBST( BinaryTreeNode*& p, int key )
{
if( p )
{
if( key < p->m_Data )
{
RemoveFromBST( p->m_Left, key );
}
else if( key > p->m_Data )
{
RemoveFromBST( p->m_Right, key );
}
else
{
if( p->m_Right )
{
BinaryTreeNode* small = FindMinNode( p->m_Right );
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
}
else if( p->m_Left )
{
BinaryTreeNode* temp = p;
p = p->m_Left;
delete temp;
temp = NULL;
}
else
{
delete p;
p = NULL;
}
}
}
}
是这样吗？
{
if( p )
{
if( key < p->m_Data )
{
RemoveFromBST( p->m_Left, key );
}
else if( key > p->m_Data )
{
RemoveFromBST( p->m_Right, key );
}
else
{
if( p->m_Right )
{
BinaryTreeNode* small = FindMinNode( p->m_Right );
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
}
else if( p->m_Left )
{
BinaryTreeNode* temp = p;
p = p->m_Left;
delete temp;
temp = NULL;
}
else
{
delete p;
p = NULL;
}
}
}
}
是这样吗？
g*s
3 楼
很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
a*n
4 楼
是的，
否则也不要gdb了，写了就bug free.
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
否则也不要gdb了，写了就bug free.
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
x*w
5 楼
一个node有parent指针，
原型是remove_node(NODE* root, NODE* pNode2Remove)
【在 a********n 的大作中提到】
: void RemoveFromBST( BinaryTreeNode*& p, int key )
: {
: if( p )
: {
: if( key < p->m_Data )
: {
: RemoveFromBST( p->m_Left, key );
: }
: else if( key > p->m_Data )
: {
p*2
6 楼
有parent没有必要要root吧？
【在 x*********w 的大作中提到】
:
: 一个node有parent指针，
: 原型是remove_node(NODE* root, NODE* pNode2Remove)
l*8
7 楼
我写了个平铺直叙版的，代码稍长。
假设BST里面没有重复value
TreeNode * deleteNode(TreeNode * root, int target) {
if (!root)
return NULL;
if (target < root->val) {
root->left = deleteNode(root->left, target);
return root;
}
if (target > root->val) {
root->right = deleteNode(root->right, target);
return root;
}
TreeNode * newRoot;
if (root->left == NULL) {
newRoot = root->right;
delete root;
return newRoot;
}
if (root->right == NULL) {
newRoot = root->left;
delete root;
return newRoot;
}
newRoot = root->right;
if (newRoot->left == NULL) {
newRoot->left = root->left;
delete root;
return newRoot;
}
TreeNode * parent = newRoot;
while(newRoot->left != NULL){
parent = newRoot;
newRoot = newRoot->left;
}
parent->left = newRoot->right;
newRoot->left = root->left;
newRoot->right = root->right;
delete root;
return newRoot;
}
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
假设BST里面没有重复value
TreeNode * deleteNode(TreeNode * root, int target) {
if (!root)
return NULL;
if (target < root->val) {
root->left = deleteNode(root->left, target);
return root;
}
if (target > root->val) {
root->right = deleteNode(root->right, target);
return root;
}
TreeNode * newRoot;
if (root->left == NULL) {
newRoot = root->right;
delete root;
return newRoot;
}
if (root->right == NULL) {
newRoot = root->left;
delete root;
return newRoot;
}
newRoot = root->right;
if (newRoot->left == NULL) {
newRoot->left = root->left;
delete root;
return newRoot;
}
TreeNode * parent = newRoot;
while(newRoot->left != NULL){
parent = newRoot;
newRoot = newRoot->left;
}
parent->left = newRoot->right;
newRoot->left = root->left;
newRoot->right = root->right;
delete root;
return newRoot;
}
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
l*8
8 楼
哦，原型是这样啊。刚才没看到
【在 x*********w 的大作中提到】
:
: 一个node有parent指针，
: 原型是remove_node(NODE* root, NODE* pNode2Remove)
【在 x*********w 的大作中提到】
:
: 一个node有parent指针，
: 原型是remove_node(NODE* root, NODE* pNode2Remove)
x*w
9 楼
不需要，你做做？
【在 p*****2 的大作中提到】
:
: 有parent没有必要要root吧？
p*2
10 楼
把left和rightmerge一下，然后把结果覆盖自己就可以了。
因为有parent，所以可以很容易知道自己是parent的left还是right，set一下就可以了
。
【在 x*********w 的大作中提到】
:
: 不需要，你做做？
x*w
11 楼
复杂度太大了吧，有标准算法
【在 p*****2 的大作中提到】
:
: 把left和rightmerge一下，然后把结果覆盖自己就可以了。
: 因为有parent，所以可以很容易知道自己是parent的left还是right，set一下就可以了
: 。
x*w
12 楼
写了一个：
static public void transplant(NODE p1, NODE p2)
{
if (p1 == null || p2 == null || p1 == p2)
return;
p2.prt = p1.prt;
if (p1.prt != null)
{
if (p1 == p1.prt.lft)
p1.prt.lft = p2;
else
p1.prt.rgt = p2;
}
p2.prt = null;
}
static public NODE delete(NODE node)
{
if (null == node)
return null;
boolean bRoot = node.prt == null;
if (node.lft == null || node.rgt == null)
{
NODE tmp = node.lft == null ? node.rgt : node.lft;
transplant(node, tmp);
if (bRoot)
return tmp;
}
else
{
NODE p = node.rgt;
while (p.lft != null)
p = p.lft;
if (p.prt != node)
{
if (p.rgt != null)
p.rgt.prt = p.prt;
p.prt.lft = p.rgt;
p.rgt = node.rgt;
}
p.lft = node.lft;
node.lft.prt = p;
transplant(node, p);
if (bRoot)
return p;
}
return null;
}
static public void transplant(NODE p1, NODE p2)
{
if (p1 == null || p2 == null || p1 == p2)
return;
p2.prt = p1.prt;
if (p1.prt != null)
{
if (p1 == p1.prt.lft)
p1.prt.lft = p2;
else
p1.prt.rgt = p2;
}
p2.prt = null;
}
static public NODE delete(NODE node)
{
if (null == node)
return null;
boolean bRoot = node.prt == null;
if (node.lft == null || node.rgt == null)
{
NODE tmp = node.lft == null ? node.rgt : node.lft;
transplant(node, tmp);
if (bRoot)
return tmp;
}
else
{
NODE p = node.rgt;
while (p.lft != null)
p = p.lft;
if (p.prt != node)
{
if (p.rgt != null)
p.rgt.prt = p.prt;
p.prt.lft = p.rgt;
p.rgt = node.rgt;
}
p.lft = node.lft;
node.lft.prt = p;
transplant(node, p);
if (bRoot)
return p;
}
return null;
}
p*2
13 楼
O(n)复杂度。算大吗？
【在 x*********w 的大作中提到】
: 写了一个：
: static public void transplant(NODE p1, NODE p2)
: {
: if (p1 == null || p2 == null || p1 == p2)
: return;
:
: p2.prt = p1.prt;
: if (p1.prt != null)
: {
: if (p1 == p1.prt.lft)
p*2
14 楼
你这个不是也没有root做输入参数吗？
【在 x*********w 的大作中提到】
: 写了一个：
: static public void transplant(NODE p1, NODE p2)
: {
: if (p1 == null || p2 == null || p1 == p2)
: return;
:
: p2.prt = p1.prt;
: if (p1.prt != null)
: {
: if (p1 == p1.prt.lft)
s*y
15 楼
Should the following code:
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
to be:
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, small->m_Data );
?
【在 a********n 的大作中提到】
: void RemoveFromBST( BinaryTreeNode*& p, int key )
: {
: if( p )
: {
: if( key < p->m_Data )
: {
: RemoveFromBST( p->m_Left, key );
: }
: else if( key > p->m_Data )
: {
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, p->m_Data );
to be:
p->m_Data = small->m_Data;
RemoveFromBST( p->m_Right, small->m_Data );
?
【在 a********n 的大作中提到】
: void RemoveFromBST( BinaryTreeNode*& p, int key )
: {
: if( p )
: {
: if( key < p->m_Data )
: {
: RemoveFromBST( p->m_Left, key );
: }
: else if( key > p->m_Data )
: {
p*2
16 楼
merge=(node1, node2)->
return node2 if !node1
return node1 if !node2
node1.right=merge(node1.right,node2)
return node1
deleteNode=(root, val)->
if(root.val==val)
root=merge(root.left,root.right)
else if(val
else
root.right=deleteNode(root.right,val)
return root
return node2 if !node1
return node1 if !node2
node1.right=merge(node1.right,node2)
return node1
deleteNode=(root, val)->
if(root.val==val)
root=merge(root.left,root.right)
else if(val
else
root.right=deleteNode(root.right,val)
return root
x*w
17 楼
我靠，你这个写的也太随便了，O(n)还想当的不平衡
【在 p*****2 的大作中提到】
: merge=(node1, node2)->
: return node2 if !node1
: return node1 if !node2
: node1.right=merge(node1.right,node2)
: return node1
: deleteNode=(root, val)->
: if(root.val==val)
: root=merge(root.left,root.right)
: else if(val
p*2
18 楼
本来就是BST，不是red-black吧？
【在 x*********w 的大作中提到】
:
: 我靠，你这个写的也太随便了，O(n)还想当的不平衡
d*x
19 楼
前几天不是有人恶心过了吗
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
【在 x*********w 的大作中提到】
: delete node from BST.
: 不能直接copy value.
: 二爷来做一下吧...
d*x
20 楼
heapify很好写
这个难写因为corner case多
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
这个难写因为corner case多
【在 g*******s 的大作中提到】
: 很多很基本的text book题逻辑简单，但写起来真的很难直接bug free。
: 这个题就是之一把。。。。还有什么heapify， non-recursive traversal 之类的
相关阅读
版面搜索为什么显示“抱歉, 您不能访问该版面(版面可能已经被屏蔽)!!”？？急问，I797a原件丢了怎么办理延期阿，附带的I94到是有的Accept，签了A的Offer，又收到别的Offer，还能再跟A讲价吗？猎头介绍的onsite完公司通知猎头？还有，求教啊 最近没事干 找工作也没啥进展 哪有当码工的学习资料？面过Storm8的同学请进签了offer letter后，也定了start date，下一步是什么？跪求Salesforce 内推G家面经想问问找工作的事, 通讯本科, 5年工作经验求Bloomberg software developer referJava Job OpportunityG家社招是先分组还是决定给offer了再分配组发Q家面经intc的process engineer每天要在clean room待多久contract的位置会lay off吗大家骑驴找马都有对口的马找么?[求解]codility online test的cannon打炮问题请问storm8 面试是不是改版了？哲學博士(Philosophy PHD)畢業怎麼找工作？？？