编程题 53 /104

给定一个升序排序的数组，将其转化为平衡二叉搜索树（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}，如下图所示：

返回任意一种即可。

参考答案

利用平衡二叉树的中序遍历是升序的性质，二分+递归解决。

查看讨论

上一题下一题

扫一扫，把题目装进口袋