108.将有序数组转换成二叉搜索树

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

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

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

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

0

/
-3 9 / / -10 5 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

将有序数组转换为二叉搜索树的结果为什么不唯一？

对于偶数个数的数组，要么选择中间节点位置左边的元素作为根节点，要么选择中间节点的右边元素作为根节点，不同的方案会创建不同的二叉树。

中序遍历不能唯一确定一棵二叉搜索树
前序和后序遍历不能确定唯一一棵二叉搜索树
前序/后序和中序可以唯一确定一棵二叉树。

因此，有序数组 -> BST 有多种答案。

以下题解，当偶数时，选择中间节点右边的元素作为根节点

找到中间元素，根据中间元素创建根节点
根据中间元素把有序数组分为两部分，左边为根节点的左子树，右边为根节点的右子树。
递归分别得到左子树和右子树。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        return sortedArray(nums,0,nums.length);
    }

    // 左闭右开
    public TreeNode sortedArray(int[] nums, int begain, int end){

        if (begain >= end) return null;

        int mid = (begain + end) >> 1;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArray(nums,begain,mid);
        root.right = sortedArray(nums,mid + 1, end);

        return root;
    }

时间复杂度: O(N), 每个元素都要访问一次

空间复杂度: O(N), 二叉搜索树空间 O(N), 递归栈深度 O(log N).

Contents

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

题解：