自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

如何刪除二叉搜索樹(shù)中的節(jié)點(diǎn)？

作者： 程序員Carl
開(kāi)發(fā) 前端
給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二叉搜索樹(shù)的性質(zhì)不變。返回二叉搜索樹(shù)(有可能被更新)的根節(jié)點(diǎn)的引用。

[[421470]]

二叉搜索樹(shù)刪除節(jié)點(diǎn)就涉及到結(jié)構(gòu)調(diào)整了!

刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

題目鏈接：https://leetcode-cn.com/problems/delete-node-in-a-bst/

給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二叉搜索樹(shù)的性質(zhì)不變。返回二叉搜索樹(shù)(有可能被更新)的根節(jié)點(diǎn)的引用。

一般來(lái)說(shuō)，刪除節(jié)點(diǎn)可分為兩個(gè)步驟：

首先找到需要?jiǎng)h除的節(jié)點(diǎn);如果找到了，刪除它。說(shuō)明：要求算法時(shí)間復(fù)雜度為 O(h)，h 為樹(shù)的高度。

示例:

思路

搜索樹(shù)的節(jié)點(diǎn)刪除要比節(jié)點(diǎn)增加復(fù)雜的多，有很多情況需要考慮，做好心里準(zhǔn)備。

遞歸

遞歸三部曲：

  • 確定遞歸函數(shù)參數(shù)以及返回值

說(shuō)道遞歸函數(shù)的返回值，在二叉樹(shù)：搜索樹(shù)中的插入操作中通過(guò)遞歸返回值來(lái)加入新節(jié)點(diǎn)， 這里也可以通過(guò)遞歸返回值刪除節(jié)點(diǎn)。

代碼如下：

  1. TreeNode* deleteNode(TreeNode* root, int key) 
  • 確定終止條件

遇到空返回，其實(shí)這也說(shuō)明沒(méi)找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了

  1. if (root == nullptr) return root; 
  • 確定單層遞歸的邏輯

這里就把平衡二叉樹(shù)中刪除節(jié)點(diǎn)遇到的情況都搞清楚。

有以下五種情況：

  • 第一種情況：沒(méi)找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了
    • 找到刪除的節(jié)點(diǎn)
  • 第二種情況：左右孩子都為空(葉子節(jié)點(diǎn))，直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn)
  • 第三種情況：刪除節(jié)點(diǎn)的左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位，返回右孩子為根節(jié)點(diǎn)
  • 第四種情況：刪除節(jié)點(diǎn)的右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn)
  • 第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹(shù)頭結(jié)點(diǎn)(左孩子)放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子上，返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。

第五種情況有點(diǎn)難以理解，看下面動(dòng)畫(huà)：

刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

動(dòng)畫(huà)中顆二叉搜索樹(shù)中，刪除元素7， 那么刪除節(jié)點(diǎn)(元素7)的左孩子就是5，刪除節(jié)點(diǎn)(元素7)的右子樹(shù)的最左面節(jié)點(diǎn)是元素8。

將刪除節(jié)點(diǎn)(元素7)的左孩子放到刪除節(jié)點(diǎn)(元素7)的右子樹(shù)的最左面節(jié)點(diǎn)(元素8)的左孩子上，就是把5為根節(jié)點(diǎn)的子樹(shù)移到了8的左孩子的位置。

要?jiǎng)h除的節(jié)點(diǎn)(元素7)的右孩子(元素9)為新的根節(jié)點(diǎn)。.

這樣就完成刪除元素7的邏輯，最好動(dòng)手畫(huà)一個(gè)圖，嘗試刪除一個(gè)節(jié)點(diǎn)試試。

代碼如下：

  1. if (root->val == key) { 
  2.     // 第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn) 
  3.     // 第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 ，返回右孩子為根節(jié)點(diǎn) 
  4.     if (root->left == nullptr) return root->right; 
  5.     // 第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn) 
  6.     else if (root->right == nullptr) return root->left; 
  7.     // 第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹(shù)放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子的位置 
  8.     // 并返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。 
  9.     else { 
  10.         TreeNode* cur = root->right; // 找右子樹(shù)最左面的節(jié)點(diǎn) 
  11.         while(cur->left != nullptr) { 
  12.             cur = cur->left; 
  13.         } 
  14.         cur->left = root->left; // 把要?jiǎng)h除的節(jié)點(diǎn)（root）左子樹(shù)放在cur的左孩子的位置 
  15.         TreeNode* tmp = root;   // 把root節(jié)點(diǎn)保存一下，下面來(lái)刪除 
  16.         root = root->right;     // 返回舊root的右孩子作為新root 
  17.         delete tmp;             // 釋放節(jié)點(diǎn)內(nèi)存（這里不寫(xiě)也可以，但C++最好手動(dòng)釋放一下吧） 
  18.         return root; 
  19.     } 
  20. } 

這里相當(dāng)于把新的節(jié)點(diǎn)返回給上一層，上一層就要用 root->left 或者 root->right接住，代碼如下：

  1. if (root->val > key) root->left = deleteNode(root->left, key); 
  2. if (root->val < key) root->right = deleteNode(root->right, key); 
  3. return root; 

整體代碼如下：(注釋中：情況1，2，3，4，5和上面分析嚴(yán)格對(duì)應(yīng))

  1. class Solution { 
  2. public: 
  3.     TreeNode* deleteNode(TreeNode* root, int key) { 
  4.         if (root == nullptr) return root; // 第一種情況：沒(méi)找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了 
  5.         if (root->val == key) { 
  6.             // 第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn) 
  7.             // 第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 ，返回右孩子為根節(jié)點(diǎn) 
  8.             if (root->left == nullptr) return root->right; 
  9.             // 第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn) 
  10.             else if (root->right == nullptr) return root->left; 
  11.             // 第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹(shù)放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子的位置 
  12.             // 并返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。 
  13.             else { 
  14.                 TreeNode* cur = root->right; // 找右子樹(shù)最左面的節(jié)點(diǎn) 
  15.                 while(cur->left != nullptr) { 
  16.                     cur = cur->left; 
  17.                 } 
  18.                 cur->left = root->left; // 把要?jiǎng)h除的節(jié)點(diǎn)（root）左子樹(shù)放在cur的左孩子的位置 
  19.                 TreeNode* tmp = root;   // 把root節(jié)點(diǎn)保存一下，下面來(lái)刪除 
  20.                 root = root->right;     // 返回舊root的右孩子作為新root 
  21.                 delete tmp;             // 釋放節(jié)點(diǎn)內(nèi)存（這里不寫(xiě)也可以，但C++最好手動(dòng)釋放一下吧） 
  22.                 return root; 
  23.             } 
  24.         } 
  25.         if (root->val > key) root->left = deleteNode(root->left, key); 
  26.         if (root->val < key) root->right = deleteNode(root->right, key); 
  27.         return root; 
  28.     } 
  29. }; 

普通二叉樹(shù)的刪除方式

這里我在介紹一種通用的刪除，普通二叉樹(shù)的刪除方式(沒(méi)有使用搜索樹(shù)的特性，遍歷整棵樹(shù))，用交換值的操作來(lái)刪除目標(biāo)節(jié)點(diǎn)。

代碼中目標(biāo)節(jié)點(diǎn)(要?jiǎng)h除的節(jié)點(diǎn))被操作了兩次：

  • 第一次是和目標(biāo)節(jié)點(diǎn)的右子樹(shù)最左面節(jié)點(diǎn)交換。
  • 第二次直接被NULL覆蓋了。

思路有點(diǎn)繞，感興趣的同學(xué)可以畫(huà)圖自己理解一下。

代碼如下：(關(guān)鍵部分已經(jīng)注釋)

  1. class Solution { 
  2. public: 
  3.     TreeNode* deleteNode(TreeNode* root, int key) { 
  4.         if (root == nullptr) return root; 
  5.         if (root->val == key) { 
  6.             if (root->right == nullptr) { // 這里第二次操作目標(biāo)值：最終刪除的作用 
  7.                 return root->left; 
  8.             } 
  9.             TreeNode *cur = root->right; 
  10.             while (cur->left) { 
  11.                 cur = cur->left; 
  12.             } 
  13.             swap(root->val, cur->val); // 這里第一次操作目標(biāo)值：交換目標(biāo)值其右子樹(shù)最左面節(jié)點(diǎn)。 
  14.         } 
  15.         root->left = deleteNode(root->left, key); 
  16.         root->right = deleteNode(root->right, key); 
  17.         return root; 
  18.     } 
  19. }; 

這個(gè)代碼是簡(jiǎn)短一些，思路也巧妙，但是不太好想，實(shí)操性不強(qiáng)，推薦第一種寫(xiě)法!

迭代法

刪除節(jié)點(diǎn)的迭代法還是復(fù)雜一些的，但其本質(zhì)我在遞歸法里都介紹了，最關(guān)鍵就是刪除節(jié)點(diǎn)的操作(動(dòng)畫(huà)模擬的過(guò)程)

代碼如下：

  1. class Solution { 
  2. private: 
  3.     // 將目標(biāo)節(jié)點(diǎn)（刪除節(jié)點(diǎn)）的左子樹(shù)放到 目標(biāo)節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子位置上 
  4.     // 并返回目標(biāo)節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn) 
  5.     // 是動(dòng)畫(huà)里模擬的過(guò)程 
  6.     TreeNode* deleteOneNode(TreeNode* target) { 
  7.         if (target == nullptr) return target; 
  8.         if (target->right == nullptr) return target->left; 
  9.         TreeNode* cur = target->right; 
  10.         while (cur->left) { 
  11.             cur = cur->left; 
  12.         } 
  13.         cur->left = target->left; 
  14.         return target->right; 
  15.     } 
  16. public: 
  17.     TreeNode* deleteNode(TreeNode* root, int key) { 
  18.         if (root == nullptr) return root; 
  19.         TreeNode* cur = root; 
  20.         TreeNode* pre = nullptr; // 記錄cur的父節(jié)點(diǎn)，用來(lái)刪除cur 
  21.         while (cur) { 
  22.             if (cur->val == key) break; 
  23.             pre = cur; 
  24.             if (cur->val > key) cur = cur->left; 
  25.             else cur = cur->right; 
  26.         } 
  27.         if (pre == nullptr) { // 如果搜索樹(shù)只有頭結(jié)點(diǎn) 
  28.             return deleteOneNode(cur); 
  29.         } 
  30.         // pre 要知道是刪左孩子還是右孩子 
  31.         if (pre->left && pre->left->val == key) { 
  32.             pre->left = deleteOneNode(cur); 
  33.         } 
  34.         if (pre->right && pre->right->val == key) { 
  35.             pre->right = deleteOneNode(cur); 
  36.         } 
  37.         return root; 
  38.     } 
  39. }; 

總結(jié)

讀完本篇，大家會(huì)發(fā)現(xiàn)二叉搜索樹(shù)刪除節(jié)點(diǎn)比增加節(jié)點(diǎn)復(fù)雜的多。

因?yàn)槎嫠阉鳂?shù)添加節(jié)點(diǎn)只需要在葉子上添加就可以的，不涉及到結(jié)構(gòu)的調(diào)整，而刪除節(jié)點(diǎn)操作涉及到結(jié)構(gòu)的調(diào)整。

這里我們依然使用遞歸函數(shù)的返回值來(lái)完成把節(jié)點(diǎn)從二叉樹(shù)中移除的操作。

這里最關(guān)鍵的邏輯就是第五種情況(刪除一個(gè)左右孩子都不為空的節(jié)點(diǎn))，這種情況一定要想清楚。

而且就算想清楚了，對(duì)應(yīng)的代碼也未必可以寫(xiě)出來(lái)，所以這道題目即考察思維邏輯，也考察代碼能力。

遞歸中我給出了兩種寫(xiě)法，推薦大家學(xué)會(huì)第一種(利用搜索樹(shù)的特性)就可以了，第二種遞歸寫(xiě)法其實(shí)是比較繞的。

最后我也給出了相應(yīng)的迭代法，就是模擬遞歸法中的邏輯來(lái)刪除節(jié)點(diǎn)，但需要一個(gè)pre記錄cur的父節(jié)點(diǎn)，方便做刪除操作。

迭代法其實(shí)不太容易寫(xiě)出來(lái)，所以如果是初學(xué)者的話，徹底掌握第一種遞歸寫(xiě)法就夠了。

其他語(yǔ)言版本

Java

  1. class Solution { 
  2.     public TreeNode deleteNode(TreeNode root, int key) { 
  3.         root = delete(root,key); 
  4.         return root; 
  5.     } 
  6.  
  7.     private TreeNode delete(TreeNode root, int key) { 
  8.         if (root == null) return null; 
  9.  
  10.         if (root.val > key) { 
  11.             root.left = delete(root.left,key); 
  12.         } else if (root.val < key) { 
  13.             root.right = delete(root.right,key); 
  14.         } else { 
  15.             if (root.left == null) return root.right; 
  16.             if (root.right == null) return root.left; 
  17.             TreeNode tmp = root.right; 
  18.             while (tmp.left != null) { 
  19.                 tmp = tmp.left; 
  20.             } 
  21.             root.val = tmp.val; 
  22.             root.right = delete(root.right,tmp.val); 
  23.         } 
  24.         return root; 
  25.     } 
  26. } 

Python

  1. class Solution: 
  2.     def deleteNode(self, root: TreeNode, key: int) -> TreeNode: 
  3.         if not root: return root  #第一種情況：沒(méi)找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了 
  4.         if root.val == key: 
  5.             if not root.left and not root.right:  #第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn) 
  6.                 del root 
  7.                 return None 
  8.             if not root.left and root.right:  #第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 ，返回右孩子為根節(jié)點(diǎn) 
  9.                 tmp = root 
  10.                 root = root.right 
  11.                 del tmp 
  12.                 return root 
  13.             if root.left and not root.right:  #第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn) 
  14.                 tmp = root 
  15.                 root = root.left 
  16.                 del tmp 
  17.                 return root 
  18.             else:  #第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹(shù)放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子的位置 
  19.                 v = root.right 
  20.                 while v.left: 
  21.                     v = v.left 
  22.                 v.left = root.left 
  23.                 tmp = root 
  24.                 root = root.right 
  25.                 del tmp 
  26.                 return root 
  27.         if root.val > key: root.left = self.deleteNode(root.left,key)  #左遞歸 
  28.         if root.val < key: root.right = self.deleteNode(root.right,key)  #右遞歸 
  29.         return root 

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。

 

責(zé)任編輯：武曉燕 來(lái)源： 代碼隨想錄
二叉搜索樹(shù)節(jié)點(diǎn)
相關(guān)推薦

2021-09-02 11:31:28

二叉搜索樹(shù)迭代法公共祖先

2021-08-26 11:31:11

二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)算法

2021-08-31 11:35:24

二叉搜索樹(shù)迭代法公共祖先

2022-12-26 00:51:33

雙向鏈表二叉搜索樹(shù)

2022-01-11 10:01:25

二叉搜索樹(shù)數(shù)量

2021-12-07 06:55:17

二叉搜索樹(shù)鏈表

2020-04-27 07:05:58

二叉樹(shù)左子樹(shù)右子樹(shù)

2020-10-11 16:56:48

二叉搜索樹(shù)代碼開(kāi)發(fā)

2024-01-17 07:36:50

二叉搜索聯(lián)系簿

2023-07-31 08:01:13

二叉搜索測(cè)試

2023-02-13 08:02:08

哈希函數(shù)哈希表搜索樹(shù)

2021-09-07 11:01:41

二叉搜索樹(shù)序數(shù)組

2020-12-11 09:49:29

二叉樹(shù)搜索樹(shù)數(shù)據(jù)

2021-04-06 08:20:24

二叉搜索樹(shù)數(shù)據(jù)結(jié)構(gòu)算法

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)Tree

2021-04-20 08:37:14

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)樹(shù)

2021-02-28 22:00:28

二叉樹(shù)節(jié)點(diǎn)序列

2021-09-06 10:38:50

二叉搜索樹(shù)遞歸

2021-10-11 06:38:52

遞歸二叉搜索樹(shù)

2023-08-29 08:31:13

B+樹(shù)數(shù)據(jù)索引
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)