美文网首页算法学习
算法题--将升序排列的数组转化为二叉搜索树

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

作者: 岁月如歌2020 | 来源:发表于2020-04-29 14:05 被阅读0次
    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

    相关文章

      网友评论

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

        本文链接:https://www.haomeiwen.com/subject/qpigwhtx.html