日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
修剪一棵二叉搜索樹，你會嗎？

如果不對遞歸有深刻的理解，本題有點難。單純移除一個節(jié)點那還不夠，要修剪!

10年積累的成都網(wǎng)站設計、做網(wǎng)站、成都外貿網(wǎng)站建設公司經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站制作后付款的網(wǎng)站建設流程，更有大峪免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

修剪二叉搜索樹

力扣鏈接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/

給定一個二叉搜索樹，同時給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹，使得所有節(jié)點的值在[L, R]中 (R>=L) 。你可能需要改變樹的根節(jié)點，所以結果應當返回修剪好的二叉搜索樹的新的根節(jié)點。

思路

相信看到這道題目大家都感覺是一道簡單題(事實上leetcode上也標明是簡單)。

但還真的不簡單!

遞歸法

直接想法就是：遞歸處理，然后遇到 root->val < low || root->val > high 的時候直接return NULL，一波修改，趕緊利落。

不難寫出如下代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr || root->val < low || root->val > high) return nullptr; 
    5. 
  
  
  
  
  5.         root->left = trimBST(root->left, low, high); 
    6. 
  
  
  
  
  6.         root->right = trimBST(root->right, low, high); 
    7. 
  
  
  
  
  7.         return root; 
    8. 
  
  
  
  
  8.     } 
    9. 
  
  
  
  
  9. }; 
    10.

然而[1, 3]區(qū)間在二叉搜索樹的中可不是單純的節(jié)點3和左孩子節(jié)點0就決定的，還要考慮節(jié)點0的右子樹。

我們在重新關注一下第二個示例，如圖：

669.修剪二叉搜索樹

所以以上的代碼是不可行的!

從圖中可以看出需要重構二叉樹，想想是不是本題就有點復雜了。

其實不用重構那么復雜。

在上圖中我們發(fā)現(xiàn)節(jié)點0并不符合區(qū)間要求，那么將節(jié)點0的右孩子 節(jié)點2 直接賦給 節(jié)點3的左孩子就可以了(就是把節(jié)點0從二叉樹中移除)，如圖：

669.修剪二叉搜索樹1

理解了最關鍵部分了我們在遞歸三部曲：

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

這里我們?yōu)槭裁葱枰祷刂的?

因為是要遍歷整棵樹，做修改，其實不需要返回值也可以，我們也可以完成修剪(其實就是從二叉樹中移除節(jié)點)的操作。

但是有返回值，更方便，可以通過遞歸函數(shù)的返回值來移除節(jié)點。

這樣的做法在二叉樹：搜索樹中的插入操作和二叉樹：搜索樹中的刪除操作中大家已經(jīng)了解過了。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. TreeNode* trimBST(TreeNode* root, int low, int high) 
    2.
  • 確定終止條件

修剪的操作并不是在終止條件上進行的，所以就是遇到空節(jié)點返回就可以了。

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

如果root(當前節(jié)點)的元素小于low的數(shù)值，那么應該遞歸右子樹，并返回右子樹符合條件的頭結點。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val < low) { 
    2. 
  
  
  
  
  2.     TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點 
    3. 
  
  
  
  
  3.     return right; 
    4. 
  
  
  
  
  4. } 
    5.

如果root(當前節(jié)點)的元素大于high的，那么應該遞歸左子樹，并返回左子樹符合條件的頭結點。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (root->val > high) { 
    2. 
  
  
  
  
  2.     TreeNode* left = trimBST(root->left, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點 
    3. 
  
  
  
  
  3.     return left; 
    4. 
  
  
  
  
  4. } 
    5.

接下來要將下一層處理完左子樹的結果賦給root->left，處理完右子樹的結果賦給root->right。

最后返回root節(jié)點，代碼如下：

 
 
 
 
    
  
  
  
  
  1. root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子 
    2. 
  
  
  
  
  2. root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子 
    3. 
  
  
  
  
  3. return root; 
    4.

此時大家是不是還沒發(fā)現(xiàn)這多余的節(jié)點究竟是如何從二叉樹中移除的呢?

在回顧一下上面的代碼，針對下圖中二叉樹的情況：

669.修剪二叉搜索樹1

如下代碼相當于把節(jié)點0的右孩子(節(jié)點2)返回給上一層，

 
 
 
 
    
  
  
  
  
  1. if (root->val < low) { 
    2. 
  
  
  
  
  2.     TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點 
    3. 
  
  
  
  
  3.     return right; 
    4. 
  
  
  
  
  4. } 
    5.

然后如下代碼相當于用節(jié)點3的左孩子 把下一層返回的 節(jié)點0的右孩子(節(jié)點2) 接住。

 
 
 
 
    
  
  
  
  
  1. root->left = trimBST(root->left, low, high); 
    2.

此時節(jié)點3的右孩子就變成了節(jié)點2，將節(jié)點0從二叉樹中移除了。

最后整體代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr ) return nullptr; 
    5. 
  
  
  
  
  5.         if (root->val < low) { 
    6. 
  
  
  
  
  6.             TreeNode* right = trimBST(root->right, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點 
    7. 
  
  
  
  
  7.             return right; 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.         if (root->val > high) { 
    10. 
  
  
  
  
  10.             TreeNode* left = trimBST(root->left, low, high); // 尋找符合區(qū)間[low, high]的節(jié)點 
    11. 
  
  
  
  
  11.             return left; 
    12. 
  
  
  
  
  12.         } 
    13. 
  
  
  
  
  13.         root->left = trimBST(root->left, low, high); // root->left接入符合條件的左孩子 
    14. 
  
  
  
  
  14.         root->right = trimBST(root->right, low, high); // root->right接入符合條件的右孩子 
    15. 
  
  
  
  
  15.         return root; 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17. }; 
    18.

精簡之后代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int low, int high) { 
    4. 
  
  
  
  
  4.         if (root == nullptr) return nullptr; 
    5. 
  
  
  
  
  5.         if (root->val < low) return trimBST(root->right, low, high); 
    6. 
  
  
  
  
  6.         if (root->val > high) return trimBST(root->left, low, high); 
    7. 
  
  
  
  
  7.         root->left = trimBST(root->left, low, high); 
    8. 
  
  
  
  
  8.         root->right = trimBST(root->right, low, high); 
    9. 
  
  
  
  
  9.         return root; 
    10. 
  
  
  
  
  10.     } 
    11. 
  
  
  
  
  11. }; 
    12.

只看代碼，其實不太好理解節(jié)點是符合移除的，這一塊大家可以自己在模擬模擬!

迭代法

因為二叉搜索樹的有序性，不需要使用棧模擬遞歸的過程。

在剪枝的時候，可以分為三步：

  • 將root移動到[L, R] 范圍內，注意是左閉右閉區(qū)間
  • 剪枝左子樹
  • 剪枝右子樹

代碼如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* trimBST(TreeNode* root, int L, int R) { 
    4. 
  
  
  
  
  4.         if (!root) return nullptr; 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.         // 處理頭結點，讓root移動到[L, R] 范圍內，注意是左閉右閉 
    7. 
  
  
  
  
  7.         while (root != nullptr && (root->val < L || root->val > R)) { 
    8. 
  
  
  
  
  8.             if (root->val < L) root = root->right; // 小于L往右走 
    9. 
  
  
  
  
  9.             else root = root->left; // 大于R往左走 
    10. 
  
  
  
  
  10.         } 
    11. 
  
  
  
  
  11.         TreeNode *cur = root; 
    12. 
  
  
  
  
  12.         // 此時root已經(jīng)在[L, R] 范圍內，處理左孩子元素小于L的情況 
    13. 
  
  
  
  
  13.         while (cur != nullptr) { 
    14. 
  
  
  
  
  14.             while (cur->left && cur->left->val < L) { 
    15. 
  
  
  
  
  15.                 cur->left = cur->left->right; 
    16. 
  
  
  
  
  16.             } 
    17. 
  
  
  
  
  17.             cur = cur->left; 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19.         cur = root; 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21.         // 此時root已經(jīng)在[L, R] 范圍內，處理右孩子大于R的情況 
    22. 
  
  
  
  
  22.         while (cur != nullptr) { 
    23. 
  
  
  
  
  23.             while (cur->right && cur->right->val > R) { 
    24. 
  
  
  
  
  24.                 cur->right = cur->right->left; 
    25. 
  
  
  
  
  25.             } 
    26. 
  
  
  
  
  26.             cur = cur->right; 
    27. 
  
  
  
  
  27.         } 
    28. 
  
  
  
  
  28.         return root; 
    29. 
  
  
  
  
  29.     } 
    30. 
  
  
  
  
  30. }; 
    31.

總結

修剪二叉搜索樹其實并不難，但在遞歸法中大家可看出我費了很大的功夫來講解如何刪除節(jié)點的，這個思路其實是比較繞的。

最終的代碼倒是很簡潔。

如果不對遞歸有深刻的理解，這道題目還是有難度的!

本題我依然給出遞歸法和迭代法，初學者掌握遞歸就可以了，如果想進一步學習，就把迭代法也寫一寫。

其他語言版本

Java

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public TreeNode trimBST(TreeNode root, int low, int high) { 
    3. 
  
  
  
  
  3.         if (root == null) { 
    4. 
  
  
  
  
  4.             return null; 
    5. 
  
  
  
  
  5.         } 
    6. 
  
  
  
  
  6.         if (root.val < low) { 
    7. 
  
  
  
  
  7.             return trimBST(root.right, low, high); 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.         if (root.val > high) { 
    10. 
  
  
  
  
  10.             return trimBST(root.left, low, high); 
    11. 
  
  
  
  
  11.         } 
    12. 
  
  
  
  
  12.         // root在[low,high]范圍內 
    13. 
  
  
  
  
  13.         root.left = trimBST(root.left, low, high); 
    14. 
  
  
  
  
  14.         root.right = trimBST(root.right, low, high); 
    15. 
  
  
  
  
  15.         return root; 
    16. 
  
  
  
  
  16.     } 
    17. 
  
  
  
  
  17. } 
    18.

Python

 
 
 
 
    
  
  
  
  
  1. class Solution: 
    2. 
  
  
  
  
  2.     def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode: 
    3. 
  
  
  
  
  3.         if not root: return root 
    4. 
  
  
  
  
  4.         if root.val < low: 
    5. 
  
  
  
  
  5.             return self.trimBST(root.right,low,high)  // 尋找符合區(qū)間[low, high]的節(jié)點 
    6. 
  
  
  
  
  6.         if root.val > high: 
    7. 
  
  
  
  
  7.             return self.trimBST(root.left,low,high)  // 尋找符合區(qū)間[low, high]的節(jié)點 
    8. 
  
  
  
  
  8.         root.left = self.trimBST(root.left,low,high)  // root->left接入符合條件的左孩子 
    9. 
  
  
  
  
  9.         root.right = self.trimBST(root.right,low,high)   // root->right接入符合條件的右孩子 
    10. 
  
  
  
  
  10.         return root 
    11.

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯(lián)系代碼隨想錄公眾號。


網(wǎng)站名稱：修剪一棵二叉搜索樹，你會嗎？
當前路徑：http://www.5511xx.com/article/cdioiej.html