LeetCode 108. Convert Sorted Array to Binary Search Tree

题目

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

分析

给定一个升序数组,将其转化成一个(高度)平衡二叉搜索树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root

点评

因为要求是平衡的,也就是最大高度和最小高度差值最大为 1,所以需要从数组的中间值开始构建。
要求是二叉搜索树(中序遍历的结果是升序的),可以分别构建根节点和左右子树根节点,递归时每次传递左右子树的所有节点的升序数组。