将有序数组转换为二叉搜索树

构造二叉搜索树，一不小心就平衡了

创新互联主营綦江网站建设的网络公司,主营网站建设方案,重庆App定制开发,綦江h5成都微信小程序搭建,綦江网站营销推广欢迎綦江等地区企业咨询

将有序数组转换为二叉搜索树

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

思路

做这道题目之前大家可以了解一下这几道：

  • 从中序与后序遍历序列构造二叉树
  • 最大二叉树
  • 二叉搜索树中的插入操作
  • 删除二叉搜索树中的节点

进入正题：

题目中说要转换为一棵高度平衡二叉搜索树。这和转换为一棵普通二叉搜索树有什么差别呢?

其实这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取，所以想构成不平衡的二叉树是自找麻烦。

在二叉树：构造二叉树登场!和二叉树：构造一棵最大的二叉树中其实已经讲过了，如果根据数组构造一颗二叉树。

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

本题其实要比二叉树：构造二叉树登场! 和 二叉树：构造一棵最大的二叉树简单一些，因为有序数组构造二叉搜索树，寻找分割点就比较容易了。

分割点就是数组中间位置的节点。

那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个?

取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

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

如下两棵树，都是这个数组的平衡二叉搜索树：

将有序数组转换为二叉搜索树

如果要分割的数组长度为偶数的时候，中间元素为两个，是取左边元素 就是树1，取右边元素就是树2。

这也是题目中强调答案不是唯一的原因。理解这一点，这道题目算是理解到位了。

递归

递归三部曲：

  • 确定递归函数返回值及其参数

删除二叉树节点，增加二叉树节点，都是用递归函数的返回值来完成，这样是比较方便的。

相信大家如果仔细看了二叉树：搜索树中的插入操作和二叉树：搜索树中的删除操作，一定会对递归函数返回值的作用深有感触。

那么本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。

再来看参数，首先是传入数组，然后就是左下表left和右下表right，我们在二叉树：构造二叉树登场!中提过，在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下表来操作原数组。

所以代码如下：

 
 
 
 
    
  
  
  
  
  1. // 左闭右闭区间[left, right] 
    2. 
  
  
  
  
  2. TreeNode* traversal(vector& nums, int left, int right) 
    3.

这里注意，我这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量。

数组：每次遇到二分法，都是一看就会，一写就废;nj 在二叉树：构造二叉树登场!，704. 二分查找 和59.螺旋矩阵II都详细讲过循环不变量。

  • 确定递归终止条件

这里定义的是左闭右闭的区间，所以当区间 left > right的时候，就是空节点了。

代码如下：

 
 
 
 
    
  
  
  
  
  1. if (left > right) return nullptr; 
    2.
  • 确定单层递归的逻辑

首先取数组中间元素的位置，不难写出int mid = (left + right) / 2;，这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法中尤其需要注意!

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

但本题leetcode的测试数据并不会越界，所以怎么写都可以。但需要有这个意识!

取了中间位置，就开始以中间位置的元素构造节点，代码：TreeNode* root = new TreeNode(nums[mid]);。

接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。

最后返回root节点，单层递归整体代码如下：

 
 
 
 
    
  
  
  
  
  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);的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的。

  • 递归整体代码如下：
 
 
 
 
    
  
  
  
  
  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.

注意：在调用traversal的时候为什么传入的left和right为什么是0和nums.size() - 1，因为定义的区间为左闭右闭。

迭代法

迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下表，一个队列放右区间下表。

模拟的就是不断分割的过程，C++代码如下：(我已经详细注释)

 
 
 
 
    
  
  
  
  
  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);   // 初始根节点 
    7. 
  
  
  
  
  7.         queue nodeQue;           // 放遍历的节点 
    8. 
  
  
  
  
  8.         queue leftQue;                 // 保存左区间下表 
    9. 
  
  
  
  
  9.         queue rightQue;                // 保存右区间下表 
    10. 
  
  
  
  
  10.         nodeQue.push(root);                 // 根节点入队列 
    11. 
  
  
  
  
  11.         leftQue.push(0);                    // 0为左区间下表初始位置 
    12. 
  
  
  
  
  12.         rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下表初始位置 
    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对应的元素给中间节点 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23.             if (left <= mid - 1) {          // 处理左区间 
    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) {         // 处理右区间 
    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.

总结

在二叉树：构造二叉树登场! 和 二叉树：构造一棵最大的二叉树之后，我们顺理成章的应该构造一下二叉搜索树了，一不小心还是一棵平衡二叉搜索树。

其实思路也是一样的，不断中间分割，然后递归处理左区间，右区间，也可以说是分治。

此时相信大家应该对通过递归函数的返回值来增删二叉树很熟悉了，这也是常规操作。

在定义区间的过程中我们又一次强调了循环不变量的重要性。

最后依然给出迭代的方法，其实就是模拟取中间元素，然后不断分割去构造二叉树的过程。

其他语言版本

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.  // 左闭右闭区间[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.   //根节点初始化 
    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.   // 根节点入队列 
    12. 
  
  
  
  
  12.   nodeQueue.offer(root); 
    13. 
  
  
  
  
  13.   // 0为左区间下表初始位置 
    14. 
  
  
  
  
  14.   leftQueue.offer(0); 
    15. 
  
  
  
  
  15.   // nums.size() - 1为右区间下表初始位置 
    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对应的元素给中间节点 
    25. 
  
  
  
  
  25.    currNode.val = nums[mid]; 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27.    // 处理左区间 
    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.    // 处理右区间 
    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  #左闭右闭的区间，当区间 left > right的时候，就是空节点,当left = right的时候，不为空 
    5. 
  
  
  
  
  5.             mid = left + (right - left) // 2 #保证数据不会越界 
    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)  #左闭右闭区间 
    12. 
  
  
  
  
  12.         return root 
    13.

本文转载自微信公众号「代码随想录」，可以通过以下二维码关注。转载本文请联系代码随想录公众号。

名称栏目：将有序数组转换为二叉搜索树
当前地址：http://www.csdahua.cn/qtweb/news26/153326.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

响应式网站知识

分类信息网站

四川内江电信机房　　 　成都IDC机房托管　　 　成都展柜设计公司　　 　网络推广公司　　 　内江托管服务器　　 　保温橡塑管　　 　内江服务器托管　　 　java虚拟主机　　 　古巴雪茄　　 　成都画册制作　　 　信衡房屋鉴定　　 　郫县封阳台　　 　广安网站设计　　 　成都网站运营维护　　 　柔性防护网　　 　自适应网站　　 　网站seo优化　　 　成都酒店服定制　　 　重庆网站设计　　 　香港虚拟主机腾讯云