第一部是先遞歸遍歷找到key == root->val;
刪除一個(gè)節(jié)點(diǎn)有以下情況：
1偷办，node->right == NULL node->left == NULL
直接刪除
2艰额，node->right 或者node->left其中一個(gè)非NULL，另外一個(gè)是NULL
直接返回子孩子得地址
3椒涯，node->left != NULL && node->right !=NULL
從右子樹里面挑選出最小的來替換掉當(dāng)前節(jié)點(diǎn)柄沮，（右子樹最左邊的節(jié)點(diǎn)），因?yàn)檫@個(gè)節(jié)點(diǎn)可以滿足大于所有的左樹和小于所有的右樹
/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
struct TreeNode* deleteNode(struct TreeNode* root, int key)
{
// base case
if (root == NULL) return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->val)
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->val)
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct TreeNode *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct TreeNode *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct TreeNode *temp ;
temp = root->right;
while(temp->left)
temp = temp->left;
// Copy the inorder successor's content to this node
root->val = temp->val;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->val);
}
return root;
}
