【朱迪的LeetCode刷题笔记】108. Convert Sorted Array to Binary Search Tree #Easy
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.Height-Balanced
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Example 1:
Input: nums = [-10,-3,0,5,9]
Output:
Explanation: is also accepted:
Example 2:
Input: nums =
Output:
Explanation: and are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 104
-104 <= nums <= 104
nums is sorted in a strictly increasing order.
Judy
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List
:rtype: TreeNode
"""
def f(nums):
l = len(nums)
if l == 1:
return TreeNode(val=nums)
elif l == 2:
return TreeNode(val=nums, left=TreeNode(val=nums))
elif l == 3:
return TreeNode(val=nums, left=TreeNode(val=nums), right=TreeNode(val=nums))
m = l // 2
return TreeNode(val=nums, left=f(nums[:m]), right=f(nums))
return f(nums)
页:
[1]