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

题目描述

给定一个严格递增的整数数组 nums，要求将其转换为 高度平衡 的 二叉搜索树（BST）。
一个高度平衡的二叉搜索树是指一个二叉树中 每个节点的左右子树高度差不超过 1。

题解思路与方法

1. 二叉搜索树（BST）的性质

• 二叉搜索树的中序遍历结果是 有序数组。

Leetcode 42.将有序数组转换为二叉搜索树-原题链接

题目内容

给你一个整数数组 $nums$，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

输入描述

• 第一行输入一个整数 n，表示数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums 的元素，按严格递增顺序排列。

输出描述

输入一行，包含 若干整数，表示二叉树的层序数组表示。 （null表示空节点，输出末尾不能有 null）

样例1

输入

5
-10 -3 0 5 9

输出

0 -3 9 -10 null 5

说明

$[0,-10,5,null,-3,null,9]$也将被视为正确答案：

样例2

输入

2
1 3

输出

3 1

说明

$[1,null,3]$ 和 $[3,1]$ 都是高度平衡二叉搜索树。

提示

• $1 <= nums.length <= 10^4$
• $-10^4 <= nums[i] <= 10^4$
• $nums$按严格递增 顺序排列