108. Convert Sorted Array to Binary Search Tree

Loading...LeetCode

理解BST性质：

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

In-order traversal of BST is an array sorted in the ascending order.

很容易想到依靠inorder 来生成树，但要达到「平衡二叉搜索树」这个条件，那左子树和右子树的数目要相等，即剩下的元素里，一半比root 小，一半比它大，那么我们只要能将所给升序序列分成一大一小的左右两半部分即可满足题目要求。

即一直确定 sorted array 的中点作为root，再以同样方法 recursively 生成左右子树，直到没元素了就停止。

切片

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return None
        mid = (len(nums)-1)//2  # 取左中点，不-1就是右中点，also works
        root = TreeNode(val = nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

helper(index)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return None
        return self.helper(nums, 0, len(nums)-1)
    
    def helper(self, arr, begin, end):
        if begin > end: return None
        mid = (begin + end) // 2
        root = TreeNode(arr[mid])
        root.left = self.helper(arr, begin, mid-1)
        root.right = self.helper(arr, mid+1, end)
        return root