算法题--将升序排列的数组转化为二叉搜索树

image.png

0. 链接

题目链接

1. 题目

2. 思路1: 递归

• 中心点作为根节点, 左侧作为左子树, 右侧作为右子树

start = 0
end = len(nums) - 1
start + (end - start + 1) >> 1

• 特殊处理包含2个数和1个数的子树, 减少判断

3. 代码

# coding:utf8
from typing import List


# 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:

        def convert(nums, start, end):
            if start < end - 1:
                mid = start + ((end - start + 1) >> 1)
                root = TreeNode(nums[mid])
                root.left = convert(nums, start, mid - 1)
                root.right = convert(nums, mid + 1, end)
                return root
            elif start == end - 1:
                root = TreeNode(nums[end])
                root.left = TreeNode(nums[start])
                return root
            elif start == end:
                root = TreeNode(nums[end])
                return root
            else:
                return None

        return convert(nums, 0, len(nums) - 1)


def print_tree(root):
    array = list()

    def preorder_traverse(node):
        array.append(node.val)
        if node.left is not None:
            preorder_traverse(node.left)
        else:
            array.append(None)
        if node.right is not None:
            preorder_traverse(node.right)
        else:
            array.append(None)

    if root is not None:
        preorder_traverse(root)
    print(array)


solution = Solution()
print_tree(solution.sortedArrayToBST([-10, -3, 0, 5, 9]))
print_tree(solution.sortedArrayToBST([0, 1, 2, 3, 4, 5]))

输出结果

[0, -3, -10, None, None, None, 9, 5, None, None, None]
[3, 1, 0, None, None, 2, None, None, 5, 4, None, None, None]

4. 结果

image.png