覺得寫的很煩燥的一題 ~___~
好多判斷式 囧
看了別人精簡的寫法，覺得會看不懂XD
感覺條列分清楚也沒什麼不好的(吧XD）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* deleteNode(struct TreeNode* root, int key){
struct TreeNode* pre = root;
struct TreeNode* ptr = root;
while (ptr!= NULL)
{
if (ptr->val== key)
break;
if (ptr->val > key)
{
pre = ptr;
ptr = ptr->left;
}
else if (ptr->val < key)
{
pre = ptr;
ptr = ptr->right;
}
}
if (ptr == NULL) //not found
return root;
//found :
if (ptr->right == NULL && ptr->left ==NULL) // no child
{
if (pre==ptr) // pre = ptr = root
{
free(root);
return NULL;
}
if (pre->left== ptr)
pre->left = NULL;
else //if (pre->right== ptr)
pre->right = NULL;
goto PtrRet;
}
if (ptr->left== NULL) // one right child
{
if (ptr==pre) // it is root
root = root->right;
else if (pre->left == ptr)
pre->left=ptr->right;
else
pre->right =ptr->right;
ptr->right = NULL;
goto PtrRet;
}
if (ptr->right== NULL) //one left child
{
if (ptr==pre) //it is root
root = root->left;
if (pre->left == ptr)
pre->left=ptr->left;
else
pre->right =ptr->left;
ptr->left = NULL;
goto PtrRet;
}
//two child , find left most big
struct TreeNode* leftMost = ptr->left;
struct TreeNode* leftMostPre = leftMost;
while (leftMost != NULL)
{
if (leftMost->right== NULL && leftMost->left == NULL)
break;
if (leftMost->right != NULL)
{
leftMostPre = leftMost;
leftMost = leftMost->right;
}
else if (leftMost->left != NULL)
break;
}
ptr->val = leftMost->val;
if (leftMostPre== leftMost) // it is the first "ptr left chile"
{
if (leftMost->left == NULL)
ptr->left=NULL;
else
{
ptr->left= leftMost->left;
leftMost->left =NULL;
}
}
else if (leftMostPre->left == leftMost)
leftMostPre->left =NULL;
else if (leftMostPre->right == leftMost)
{
if (leftMost->left != NULL)
{
leftMostPre->right = leftMost->left;
leftMost->left=NULL;
}
else
leftMostPre->right =NULL;
}
free(leftMost);
return root;
PtrRet :
free(ptr);
return root;
}
沒有留言:
張貼留言