Links

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

题目地址(108. 将有序数组转换为二叉搜索树)

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

题目描述

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • airbnb

思路

由于输入是一个升序排列的有序数组。因此任意选择一点,将其作为根节点,其左部分左节点,其右部分右节点即可。 因此我们很容易写出递归代码。
而题目要求是高度平衡的二叉搜索树,因此我们必须要取中点。 不难证明:由于是中点,因此左右两部分差不会大于 1,也就是说其形成的左右子树节点数最多相差 1,因此左右子树高度差的绝对值不超过 1
形象一点来看就像你提起一根绳子,从中点提的话才能使得两边绳子长度相差最小。
image.png

关键点

  • 找中点

代码

代码支持:JS,C++,Java,Python
JS Code:
var sortedArrayToBST = function (nums) {
// 由于数组是排序好的,因此一个思路就是将数组分成两半,一半是左子树,另一半是右子树
// 然后运用“树的递归性质”递归完成操作即可。
if (nums.length === 0) return null;
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
Python Code:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return None
mid = (len(nums) - 1) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:每次递归都 copy 了 N 的 空间,因此空间复杂度为 $O(N ^ 2)$
然而,实际上没必要开辟新的空间:
C++ Code:
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return reBuild(nums, 0, nums.size()-1);
}
TreeNode* reBuild(vector<int>& nums, int left, int right)
{
// 终止条件:中序遍历为空
if(left > right)
{
return NULL;
}
// 建立当前子树的根节点
int mid = (left+right)/2;
TreeNode * root = new TreeNode(nums[mid]);
// 左子树的下层递归
root->left = reBuild(nums, left, mid-1);
// 右子树的下层递归
root->right = reBuild(nums, mid+1, right);
// 返回根节点
return root;
}
};
Java Code:
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
private TreeNode dfs(int[] nums, int lo, int hi) {
if (lo > hi) {
return null;
}
int mid = lo + (hi - lo) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, lo, mid - 1);
root.right = dfs(nums, mid + 1, hi);
return root;
}
}
Python Code:
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.reBuild(nums, 0, len(nums)-1)
def reBuild(self, nums, left, right):
# 终止条件:
if left > right:
return
# 建立当前子树的根节点
mid = (left + right)//2
root = TreeNode(nums[mid])
# 左右子树的下层递归
root.left = self.reBuild(nums, left, mid-1)
root.right = self.reBuild(nums, mid+1, right)
return root
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:由于是平衡二叉树,因此隐式调用栈的开销为 $O(logN)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
公众号【 力扣加加】知乎专栏【 Lucifer - 知乎
点关注,不迷路!