如題：

給定一個二叉搜索樹的根節點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變。返回二叉搜索樹（有可能被更新）的根節點的引用。 一般來說，刪除節點可分為兩個步驟： 首先找到需要刪除的節點； 如果找到了，刪除它。 說明： 要求算法時間復雜度為 O(h)，h 為樹的高度。示例: root = [5,3,6,2,4,null,7] key = 35/ \3 6/ \ \ 2 4 7給定需要刪除的節點值是 3，所以我們首先找到 3 這個節點，然后刪除它。 一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。5/ \4 6/ \ 2 7 另一個正確答案是 [5,2,6,null,4,null,7]。5/ \2 6\ \4 7

簡單說就是二叉搜索樹的刪除操作，難度為中等，這個是二叉搜索樹的基本操作，掌握了就很簡單了。

刪除一個節點后要保持原有二叉樹性質，根據節點自身的情況有三種情況需要處理

如果節點沒有左右子樹，則可以直接刪除。
如果節點只有左子樹或者右子樹，則可以直接讓子樹替代自己。
如果同時存在左右節點，我們知道中序遍歷二叉樹得到有序數列，這時候有兩種操作方式，一種是使用直接前驅替代待刪節點，一種是使用直接后繼替代待刪節點。兩種方式操作邏輯一致，僅僅方向不同。
3.1 設待刪節點為delte, 如果采用直接前驅替代，這時候搜索節點左子樹最右邊的點s(s沒有右子樹),這時候有兩種情況，一種是s本身就是待刪節點的左子樹，即s的父節點等于delte，這時候令

delte->left = s->left;delte->val = s->val;即可。

如果s的父節點p不等于delte，這時候需要將s的左子樹變為p的右子樹即可。
整個代碼也比較簡單理解：

//直接前驅替代 p = delte; s = delte->left; while (s->right){p = s; s = s->right;} dlete->val = s->val; if (p == delte) delte->left = s->left; else p->right = s->left; free(s);

如果使用直接后繼替代delte的話，這時候是搜索delte的右子樹中最左邊的元素s，同樣存在兩種情況，s的父節點p等于delte或者不等于，處理上和直接前驅類似。

//直接后繼替代 p = delte; s = delte->right; while (s->left){p = s; s = s->left;} dlete->val = s->val; if (p == delte) delte->right = s->right; else p->left = s->right; free(s);

下面是直接后繼替代的代碼：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode* deleteBST(struct TreeNode* delte) {struct TreeNode *p, *t;if (!delte->right){//只有左孩子的情況t = delte; delte = delte->left;}else if (!delte->left){//只有右孩子的情況 t = delte; delte = delte->right; }else{//左右孩子都有，從右子樹搜索其直接后繼，即最左邊的元素p = delte; t = p->right;while (t->left){p = t; t = t->left;}delte->val = t->val;if (p == delte)delte->right = t->right;elsep->left = t->right;}free(t);return delte; }struct TreeNode* deleteNode(struct TreeNode* root, int key){if (!root) return root;if (root->val == key)root = deleteBST(root);else if (root->val > key)root->left = deleteNode(root->left, key);elseroot->right = deleteNode(root->right, key);return root; }

參考資料：

1.?數據結構?: C語言版/ 嚴蔚敏，吳偉民編著

2. 算法導論

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的leetcode 450. 删除二叉搜索树中的节点 c语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。