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

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

構(gòu)造二叉搜索樹，一不小心就平衡了

創(chuàng)新互聯(lián)主營綦江網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,重慶App定制開發(fā),綦江h(huán)5成都微信小程序搭建,綦江網(wǎng)站營銷推廣歡迎綦江等地區(qū)企業(yè)咨詢

將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

力扣題目鏈接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。

示例:

思路

做這道題目之前大家可以了解一下這幾道：

  • 從中序與后序遍歷序列構(gòu)造二叉樹
  • 最大二叉樹
  • 二叉搜索樹中的插入操作
  • 刪除二叉搜索樹中的節(jié)點

進(jìn)入正題：

題目中說要轉(zhuǎn)換為一棵高度平衡二叉搜索樹。這和轉(zhuǎn)換為一棵普通二叉搜索樹有什么差別呢?

其實這里不用強調(diào)平衡二叉搜索樹，數(shù)組構(gòu)造二叉樹，構(gòu)成平衡樹是自然而然的事情，因為大家默認(rèn)都是從數(shù)組中間位置取值作為節(jié)點元素，一般不會隨機取，所以想構(gòu)成不平衡的二叉樹是自找麻煩。

在二叉樹：構(gòu)造二叉樹登場!和二叉樹：構(gòu)造一棵最大的二叉樹中其實已經(jīng)講過了，如果根據(jù)數(shù)組構(gòu)造一顆二叉樹。

本質(zhì)就是尋找分割點，分割點作為當(dāng)前節(jié)點，然后遞歸左區(qū)間和右區(qū)間。

本題其實要比二叉樹：構(gòu)造二叉樹登場! 和 二叉樹：構(gòu)造一棵最大的二叉樹簡單一些，因為有序數(shù)組構(gòu)造二叉搜索樹，尋找分割點就比較容易了。

分割點就是數(shù)組中間位置的節(jié)點。

那么為問題來了，如果數(shù)組長度為偶數(shù)，中間節(jié)點有兩個，取哪一個?

取哪一個都可以，只不過構(gòu)成了不同的平衡二叉搜索樹。

例如：輸入：[-10,-3,0,5,9]

如下兩棵樹，都是這個數(shù)組的平衡二叉搜索樹：

將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

如果要分割的數(shù)組長度為偶數(shù)的時候，中間元素為兩個，是取左邊元素 就是樹1，取右邊元素就是樹2。

這也是題目中強調(diào)答案不是唯一的原因。理解這一點，這道題目算是理解到位了。

遞歸

遞歸三部曲：

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

刪除二叉樹節(jié)點，增加二叉樹節(jié)點，都是用遞歸函數(shù)的返回值來完成，這樣是比較方便的。

相信大家如果仔細(xì)看了二叉樹：搜索樹中的插入操作和二叉樹：搜索樹中的刪除操作，一定會對遞歸函數(shù)返回值的作用深有感觸。

那么本題要構(gòu)造二叉樹，依然用遞歸函數(shù)的返回值來構(gòu)造中節(jié)點的左右孩子。

再來看參數(shù)，首先是傳入數(shù)組，然后就是左下表left和右下表right，我們在二叉樹：構(gòu)造二叉樹登場!中提過，在構(gòu)造二叉樹的時候盡量不要重新定義左右區(qū)間數(shù)組，而是用下表來操作原數(shù)組。

所以代碼如下：

 
 
 
 
    
  
  
  
  
  1. // 左閉右閉區(qū)間[left, right] 
    2. 
  
  
  
  
  2. TreeNode* traversal(vector& nums, int left, int right) 
    3.

這里注意，我這里定義的是左閉右閉區(qū)間，在不斷分割的過程中，也會堅持左閉右閉的區(qū)間，這又涉及到我們講過的循環(huán)不變量。

數(shù)組：每次遇到二分法，都是一看就會，一寫就廢;nj 在二叉樹：構(gòu)造二叉樹登場!，704. 二分查找 和59.螺旋矩陣II都詳細(xì)講過循環(huán)不變量。

  • 確定遞歸終止條件

這里定義的是左閉右閉的區(qū)間，所以當(dāng)區(qū)間 left > right的時候，就是空節(jié)點了。

代碼如下：

 
 
 
 
    
  
  
  
  
  1. if (left > right) return nullptr; 
    2.
  • 確定單層遞歸的邏輯

首先取數(shù)組中間元素的位置，不難寫出int mid = (left + right) / 2;，這么寫其實有一個問題，就是數(shù)值越界，例如left和right都是最大int，這么操作就越界了，在二分法中尤其需要注意!

所以可以這么寫：int mid = left + ((right - left) / 2);

但本題leetcode的測試數(shù)據(jù)并不會越界，所以怎么寫都可以。但需要有這個意識!

取了中間位置，就開始以中間位置的元素構(gòu)造節(jié)點，代碼：TreeNode* root = new TreeNode(nums[mid]);。

接著劃分區(qū)間，root的左孩子接住下一層左區(qū)間的構(gòu)造節(jié)點，右孩子接住下一層右區(qū)間構(gòu)造的節(jié)點。

最后返回root節(jié)點，單層遞歸整體代碼如下：

 
 
 
 
    
  
  
  
  
  1. int mid = left + ((right - left) / 2); 
    2. 
  
  
  
  
  2. TreeNode* root = new TreeNode(nums[mid]); 
    3. 
  
  
  
  
  3. root->left = traversal(nums, left, mid - 1); 
    4. 
  
  
  
  
  4. root->right = traversal(nums, mid + 1, right); 
    5. 
  
  
  
  
  5. return root; 
    6.

這里int mid = left + ((right - left) / 2);的寫法相當(dāng)于是如果數(shù)組長度為偶數(shù)，中間位置有兩個元素，取靠左邊的。

  • 遞歸整體代碼如下：
 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. private: 
    3. 
  
  
  
  
  3.     TreeNode* traversal(vector& nums, int left, int right) { 
    4. 
  
  
  
  
  4.         if (left > right) return nullptr; 
    5. 
  
  
  
  
  5.         int mid = left + ((right - left) / 2); 
    6. 
  
  
  
  
  6.         TreeNode* root = new TreeNode(nums[mid]); 
    7. 
  
  
  
  
  7.         root->left = traversal(nums, left, mid - 1); 
    8. 
  
  
  
  
  8.         root->right = traversal(nums, mid + 1, right); 
    9. 
  
  
  
  
  9.         return root; 
    10. 
  
  
  
  
  10.     } 
    11. 
  
  
  
  
  11. public: 
    12. 
  
  
  
  
  12.     TreeNode* sortedArrayToBST(vector& nums) { 
    13. 
  
  
  
  
  13.         TreeNode* root = traversal(nums, 0, nums.size() - 1); 
    14. 
  
  
  
  
  14.         return root; 
    15. 
  
  
  
  
  15.     } 
    16. 
  
  
  
  
  16. }; 
    17.

注意：在調(diào)用traversal的時候為什么傳入的left和right為什么是0和nums.size() - 1，因為定義的區(qū)間為左閉右閉。

迭代法

迭代法可以通過三個隊列來模擬，一個隊列放遍歷的節(jié)點，一個隊列放左區(qū)間下表，一個隊列放右區(qū)間下表。

模擬的就是不斷分割的過程，C++代碼如下：(我已經(jīng)詳細(xì)注釋)

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2. public: 
    3. 
  
  
  
  
  3.     TreeNode* sortedArrayToBST(vector& nums) { 
    4. 
  
  
  
  
  4.         if (nums.size() == 0) return nullptr; 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.         TreeNode* root = new TreeNode(0);   // 初始根節(jié)點 
    7. 
  
  
  
  
  7.         queue nodeQue;           // 放遍歷的節(jié)點 
    8. 
  
  
  
  
  8.         queue leftQue;                 // 保存左區(qū)間下表 
    9. 
  
  
  
  
  9.         queue rightQue;                // 保存右區(qū)間下表 
    10. 
  
  
  
  
  10.         nodeQue.push(root);                 // 根節(jié)點入隊列 
    11. 
  
  
  
  
  11.         leftQue.push(0);                    // 0為左區(qū)間下表初始位置 
    12. 
  
  
  
  
  12.         rightQue.push(nums.size() - 1);     // nums.size() - 1為右區(qū)間下表初始位置 
    13. 
  
  
  
  
  13.  
    14. 
  
  
  
  
  14.         while (!nodeQue.empty()) { 
    15. 
  
  
  
  
  15.             TreeNode* curNode = nodeQue.front(); 
    16. 
  
  
  
  
  16.             nodeQue.pop(); 
    17. 
  
  
  
  
  17.             int left = leftQue.front(); leftQue.pop(); 
    18. 
  
  
  
  
  18.             int right = rightQue.front(); rightQue.pop(); 
    19. 
  
  
  
  
  19.             int mid = left + ((right - left) / 2); 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21.             curNode->val = nums[mid];       // 將mid對應(yīng)的元素給中間節(jié)點 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23.             if (left <= mid - 1) {          // 處理左區(qū)間 
    24. 
  
  
  
  
  24.                 curNode->left = new TreeNode(0); 
    25. 
  
  
  
  
  25.                 nodeQue.push(curNode->left); 
    26. 
  
  
  
  
  26.                 leftQue.push(left); 
    27. 
  
  
  
  
  27.                 rightQue.push(mid - 1); 
    28. 
  
  
  
  
  28.             } 
    29. 
  
  
  
  
  29.  
    30. 
  
  
  
  
  30.             if (right >= mid + 1) {         // 處理右區(qū)間 
    31. 
  
  
  
  
  31.                 curNode->right = new TreeNode(0); 
    32. 
  
  
  
  
  32.                 nodeQue.push(curNode->right); 
    33. 
  
  
  
  
  33.                 leftQue.push(mid + 1); 
    34. 
  
  
  
  
  34.                 rightQue.push(right); 
    35. 
  
  
  
  
  35.             } 
    36. 
  
  
  
  
  36.         } 
    37. 
  
  
  
  
  37.         return root; 
    38. 
  
  
  
  
  38.     } 
    39. 
  
  
  
  
  39. }; 
    40.

總結(jié)

在二叉樹：構(gòu)造二叉樹登場! 和 二叉樹：構(gòu)造一棵最大的二叉樹之后，我們順理成章的應(yīng)該構(gòu)造一下二叉搜索樹了，一不小心還是一棵平衡二叉搜索樹。

其實思路也是一樣的，不斷中間分割，然后遞歸處理左區(qū)間，右區(qū)間，也可以說是分治。

此時相信大家應(yīng)該對通過遞歸函數(shù)的返回值來增刪二叉樹很熟悉了，這也是常規(guī)操作。

在定義區(qū)間的過程中我們又一次強調(diào)了循環(huán)不變量的重要性。

最后依然給出迭代的方法，其實就是模擬取中間元素，然后不斷分割去構(gòu)造二叉樹的過程。

其他語言版本

Java

遞歸: 左閉右閉 [left,right]

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.  public TreeNode sortedArrayToBST(int[] nums) { 
    3. 
  
  
  
  
  3.   TreeNode root = traversal(nums, 0, nums.length - 1); 
    4. 
  
  
  
  
  4.   return root; 
    5. 
  
  
  
  
  5.  } 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7.  // 左閉右閉區(qū)間[left, right) 
    8. 
  
  
  
  
  8.  private TreeNode traversal(int[] nums, int left, int right) { 
    9. 
  
  
  
  
  9.   if (left > right) return null; 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.   int mid = left + ((right - left) >> 1); 
    12. 
  
  
  
  
  12.   TreeNode root = new TreeNode(nums[mid]); 
    13. 
  
  
  
  
  13.   root.left = traversal(nums, left, mid - 1); 
    14. 
  
  
  
  
  14.   root.right = traversal(nums, mid + 1, right); 
    15. 
  
  
  
  
  15.   return root; 
    16. 
  
  
  
  
  16.  } 
    17. 
  
  
  
  
  17. } 
    18.

迭代: 左閉右閉 [left,right]

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.  public TreeNode sortedArrayToBST(int[] nums) { 
    3. 
  
  
  
  
  3.   if (nums.length == 0) return null; 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5.   //根節(jié)點初始化 
    6. 
  
  
  
  
  6.   TreeNode root = new TreeNode(-1); 
    7. 
  
  
  
  
  7.   Queue nodeQueue = new LinkedList<>(); 
    8. 
  
  
  
  
  8.   Queue leftQueue = new LinkedList<>(); 
    9. 
  
  
  
  
  9.   Queue rightQueue = new LinkedList<>(); 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11.   // 根節(jié)點入隊列 
    12. 
  
  
  
  
  12.   nodeQueue.offer(root); 
    13. 
  
  
  
  
  13.   // 0為左區(qū)間下表初始位置 
    14. 
  
  
  
  
  14.   leftQueue.offer(0); 
    15. 
  
  
  
  
  15.   // nums.size() - 1為右區(qū)間下表初始位置 
    16. 
  
  
  
  
  16.   rightQueue.offer(nums.length - 1); 
    17. 
  
  
  
  
  17.  
    18. 
  
  
  
  
  18.   while (!nodeQueue.isEmpty()) { 
    19. 
  
  
  
  
  19.    TreeNode currNode = nodeQueue.poll(); 
    20. 
  
  
  
  
  20.    int left = leftQueue.poll(); 
    21. 
  
  
  
  
  21.    int right = rightQueue.poll(); 
    22. 
  
  
  
  
  22.    int mid = left + ((right - left) >> 1); 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24.    // 將mid對應(yīng)的元素給中間節(jié)點 
    25. 
  
  
  
  
  25.    currNode.val = nums[mid]; 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27.    // 處理左區(qū)間 
    28. 
  
  
  
  
  28.    if (left <= mid - 1) { 
    29. 
  
  
  
  
  29.     currNode.left = new TreeNode(-1); 
    30. 
  
  
  
  
  30.     nodeQueue.offer(currNode.left); 
    31. 
  
  
  
  
  31.     leftQueue.offer(left); 
    32. 
  
  
  
  
  32.     rightQueue.offer(mid - 1); 
    33. 
  
  
  
  
  33.    } 
    34. 
  
  
  
  
  34.  
    35. 
  
  
  
  
  35.    // 處理右區(qū)間 
    36. 
  
  
  
  
  36.    if (right >= mid + 1) { 
    37. 
  
  
  
  
  37.     currNode.right = new TreeNode(-1); 
    38. 
  
  
  
  
  38.     nodeQueue.offer(currNode.right); 
    39. 
  
  
  
  
  39.     leftQueue.offer(mid + 1); 
    40. 
  
  
  
  
  40.     rightQueue.offer(right); 
    41. 
  
  
  
  
  41.    } 
    42. 
  
  
  
  
  42.   } 
    43. 
  
  
  
  
  43.   return root; 
    44. 
  
  
  
  
  44.  } 
    45. 
  
  
  
  
  45. } 
    46.

Python

遞歸法：

 
 
 
 
    
  
  
  
  
  1. class Solution: 
    2. 
  
  
  
  
  2.     def sortedArrayToBST(self, nums: List[int]) -> TreeNode: 
    3. 
  
  
  
  
  3.         def buildaTree(left,right): 
    4. 
  
  
  
  
  4.             if left > right: return None  #左閉右閉的區(qū)間，當(dāng)區(qū)間 left > right的時候，就是空節(jié)點,當(dāng)left = right的時候，不為空 
    5. 
  
  
  
  
  5.             mid = left + (right - left) // 2 #保證數(shù)據(jù)不會越界 
    6. 
  
  
  
  
  6.             val = nums[mid] 
    7. 
  
  
  
  
  7.             root = TreeNode(val) 
    8. 
  
  
  
  
  8.             root.left = buildaTree(left,mid - 1) 
    9. 
  
  
  
  
  9.             root.right = buildaTree(mid + 1,right) 
    10. 
  
  
  
  
  10.             return root 
    11. 
  
  
  
  
  11.         root = buildaTree(0,len(nums) - 1)  #左閉右閉區(qū)間 
    12. 
  
  
  
  
  12.         return root 
    13.

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


網(wǎng)站標(biāo)題：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
URL標(biāo)題：http://www.5511xx.com/article/ccshpji.html