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

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

题目描述

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

前置知识

公司

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

思路

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

关键点

  • 找中点

代码

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