力扣小白刷题之108题将有序数组转换为二叉搜索树
题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
思路
参考自：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/
二叉查找树的中序遍历是一个升序数组。因此本题等同于根据中序遍历的序列恢复二叉搜索树。
- 所以我们可以以升序序列中的任一元素作为根节点
- 以该元素左边的升序序列构建左子树
- 以该元素右边的升序序列构建右子树，
- 这样得到的树就是一棵二叉搜索树(BST)，
- 但又因为本题要求高度平衡的二叉搜索树，所以需要选择升序序列的中间元素作为根节点。