【Garen刷题笔记】LeetCode 108 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树(7.3日题)

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

示例:

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

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 解法1： 因为所给数组为有序且升序数组，而二叉搜索树的中序遍历为升序序列，所以自然想到根据中序遍历序列恢复二叉树，考虑是平衡搜索二叉树，所以这里使用二分法来确定根节点，以保证左右子树高度差不大于1。而因为选取根节点不唯一，所以生成的BST也不唯一。实际就是同一种方法的多种策略，这里只给出一种。 代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); } private TreeNode helper(int[] nums, int left, int right){ if(left > right){ return null; } int mid = (left + right) >> 1; TreeNode root = new TreeNode(nums[mid]); root.left = helper(nums, left, mid - 1); root.right = helper(nums, mid + 1,right); return root; } }

复杂度分析： 时间复杂度：含有n个元素的数组遍历，所以时间复杂度为$O(n)$。 空间复杂度：因为使用了递归，所以空间复杂度就是递归栈的深度$Ologn$。通常建立二叉树，最坏情况的递归栈深度为$O(n)$，平均情况为$O(logn)$，当二叉树为平衡二叉树时可以达到，而此题恰好要求建立平衡二叉树，所以递归栈深度认为是$logn$，空间复杂度为$O(logn)$。