我要招人

去企业版

首页 > 试题广场 >

将升序数组转化为平衡二叉搜索树

[编程题]将升序数组转化为平衡二叉搜索树

热度指数：32617 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1

数据范围： $0 \le n \le 10000$ ，数组中每个值满足 $|val| \le 5000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

例如当输入的升序数组为[-1,0,1,2]时，转化后的平衡二叉搜索树（BST）可以为{1,0,2,-1}，如下图所示：

或为{0,-1,1,#,#,#,2}，如下图所示：

返回任意一种即可。

示例1

输入

[-1,0,1,2]

输出

{1,0,2,-1}

示例2

输入

[]

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

漫漫云天自翱翔

发表于 2021-07-06 15:06:45

精华题解将升序数组转化为平衡二叉搜索树题解一：二分+递归题解思路：利用BST中序遍历为升序序列的特性。 BST中序遍历：思路分析：为了保持平衡，每次选择区间的中间值作为根节点。递归分析：递归边界： (left > right) 返回NULL；递归过程：选取展开全文

如也201810022128875

发表于 2021-07-18 00:32:17

精华题解题目描述给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）方法一：递归解题思路先了解一下平衡二叉搜索树的特点。二叉搜索树，它的中序遍历后的结果就是一个升序的序列；平衡的，说明任何一个节点的左子树和右子树的高度相差不超过1。题目中所给的是一个升序排序的数组，所以一个大体流程展开全文

江南好___

发表于 2021-07-14 23:02:18

精华题解描述题目描述给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）. 示例输入：[-1,0,1,2] 返回值：{1,0,2,-1}知识点：二叉搜索树，排序，数组，二分查找难度：⭐⭐ 题解解题思路对于有序数组，首先应该想到用二分法，接着是构造二叉搜索树的过程，应该想到用分治法，分别对左展开全文

牛一霸

发表于 2021-07-05 21:30:20

精华题解题目：将升序数组转化为平衡二叉搜索树描述：给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）. 示例1：输入：[-1,0,1,2]，返回值：{1,0,2,-1} 解法一：思路分析：二叉搜索树，又称之为二叉排序树（二叉查找树），它是一棵空树，或者是具有以下性质的展开全文

华科不平凡

发表于 2020-08-21 19:42:37

先序遍历。注意一点即可，在求中点的过程中，理论上left + (right-left) / 2和left + (right - left + 1) / 2都是合法的，但从题目中的示例可以得知，我们的代码里应使用后者才能符合题意。这有一个小插曲，刚开始我在sortedArrayToBST中写了如下展开全文

数据结构和算法

发表于 2021-08-03 14:52:34

递归方式解决题中说了要转换为一棵高度平衡的二叉搜索树，并且数组又是排过序的，这就好办了。我们可以使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值都是比他小的，作为他左子树的结点值。m后面的值都是比他大的，作为他右子树的节点值，示例中一个可能的结果是。代码如下 public 展开全文

阿虻

发表于 2022-02-17 17:02:56

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; 展开全文

scutlwy

发表于 2020-08-24 18:21:00

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Sol 展开全文

我有一个大厂梦

发表于 2021-11-29 15:32:54

题目：简单题给定一个升序数组，转化为平衡二叉搜索树。平衡：左右子树之差不大于1 思路：本题的重点是平衡二字。所以可以以数组的中心为根节点，之后递归进行操作即可。代码： /** * * @param num int整型一维数组 * @return Tr 展开全文

猫头鹰的咖啡馆

发表于 2021-10-22 15:51:54

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @ 展开全文

youyouhuo

发表于 2021-05-06 20:32:48

首先理解一下平衡二叉搜索树（BST），看题中给的例子：输入：[-1,0,1,2]输出：{1,0,2,-1}也就是图比较丑，根节点取值为1，最后一层节点是-1。然后，结合题目，需要根据输入来构建输出，那关键点就是确定根节点，因为得到根节点后，序列就分为【左子树跟节点右子树】了，然后递归调用就展开全文

牛客877483763号

发表于 2021-12-20 11:18:00

将升序数组转化为平衡二叉搜索树描述给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）. 平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1 数据范围：0≤n≤10000 展开全文