无聊的刷题笔记

Convert Sorted Array to Binary Search Tree

LeetCode 108

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.

不使用下标索引直接使用nums递归会超内存

# 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
"""
return self.sortedArrayToBST_LR(nums, 0, len(nums)-1)

def sortedArrayToBST_LR(self, nums, left, right):
if left>right:
return None
elif left<right:
mid = (left+right)/2
node = TreeNode(nums[mid])
node.left = self.sortedArrayToBST_LR(nums, left, mid-1)
node.right = self.sortedArrayToBST_LR(nums, mid+1, right)
else:
return TreeNode(nums[left])
return node