刪除一個二叉搜索樹中的節(jié)點，需要進(jìn)行情況的分類討論，看一下將這個節(jié)點刪除之后是否需要對二叉搜索樹進(jìn)行調(diào)整（為了保持樹的連接和維持二叉搜索樹的性質(zhì)）。

（1）如果刪除的是一個葉子節(jié)點，那問題不大，因為它沒有左子樹和右子樹，直接返回NULL就行了，表示它沒了。

（2）如果要刪除的節(jié)點，左右子樹都存在，那麻煩了，刪除這個節(jié)點是需要進(jìn)行調(diào)整的，刪除的這個節(jié)點可以用它左子樹的最大值或者右子樹的最小值來替代（為了 維持二叉搜索樹的性質(zhì)），這里我們用右子樹的最小值來代替這個被刪除的最小值。然后遞歸地到右子樹刪除那個原來右子樹中的最小值（因為它已經(jīng)滾到那個被刪除的節(jié)點上了）。

（3）如果要刪除的節(jié)點左子樹不存在，那我們直接讓這個被刪除的節(jié)點的父節(jié)點的右指針指向被刪除節(jié)點的右孩子就好了。也就是跳過了這個被刪除的節(jié)點，表示這個節(jié)點被刪除了。 這一步操作直接用root = root -> right;就可以完成。

（4）如果被刪除的節(jié)點右子樹不存在，那就類似（3），直接用root = root -> left;表示將被刪除的節(jié)點的父節(jié)點的左指針指向被刪除節(jié)點的左孩子，表示將這個節(jié)點刪除。

代碼如下：

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:TreeNode* findSmallest(TreeNode* root) { // 找到以root為根的樹中的最小值，這個函數(shù)是為了在刪除某個節(jié)點且這個節(jié)點右子樹不為空時，找到右子樹中的最小值if(root == NULL) { return NULL;} else if(root -> left != NULL) { // 如果左子樹不為空，這最小值在左子樹中，遞歸地去左子樹中尋找最小值return findSmallest(root -> left);}return root; // 如果左子樹為空，這最小值就是root，這是由二叉搜索樹的性質(zhì)決定的}TreeNode* deleteNode(TreeNode* root, int key) {if(root == NULL) {return NULL;} else if(key < root -> val) { // 要刪除的值小于根節(jié)點的值，遞歸地到左子樹中刪除這個節(jié)點root -> left = deleteNode(root -> left, key);} else if(key > root -> val) { // 要刪除的值大于根節(jié)點的值，遞歸地到右子樹中刪除這個節(jié)點root -> right = deleteNode(root -> right, key);} else {if(root -> left == NULL && root -> right == NULL) { // 如果被刪除的節(jié)點是葉節(jié)點，直接刪除這個節(jié)點，返回NULL即可return NULL;} else if(root -> left != NULL && root -> right != NULL) { // 如果被刪除的節(jié)點左、右子樹都不為空TreeNode* temp = findSmallest(root -> right); // 那就找到右子樹中最小的值（也就是被刪除的節(jié)點的中序后繼），用這個節(jié)點代替被刪除的節(jié)點root -> val = temp -> val; root -> right = deleteNode(root -> right, root -> val); // 然后遞歸地到右子樹中刪除這個節(jié)點} else if(root -> left != NULL) { // 如果左子樹不為空，這直接連接被刪除的節(jié)點的父節(jié)點的左指針到這個左子樹上root = root -> left;} else if(root -> right != NULL) { // 右子樹不為空時同理root = root -> right;}}return root;} };

總結(jié)

以上是生活随笔為你收集整理的java 递归从子节点删除父节点_LeetCode450. 删除二叉搜索树中的节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。