当前位置：首页 > article >正文

将有序数组转换为二叉搜索树python

article 2024/11/30 19:48:03

一、问题描述

平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

即-10，5作为根节点。

即-3，9作为根节点。

from heapq import heapify, heappop, heappush
from math import inf
from typing import List, Counter
from typing import Optional
from clang.cindex import Config

from pyasn1.compat.octets import null


nums = [-10,-3,0,5,9]



class Solution:
    def sortedArrayToBST1(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置左边的数字作为根节点
            mid = (left + right) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

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

    def sortedArrayToBST2(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置右边的数字作为根节点
            mid = (left + right + 1) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

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


def preorderTraversal(root: Optional[TreeNode]) -> List[int]:  # 前序遍历(根，左，右)
    l = []

    def tree(root):
        if not root:
            return
        l.append(root.val)
        tree(root.left)
        tree(root.right)

    tree(root)
    return l


S = Solution()
print(preorderTraversal(S.sortedArrayToBST1(nums)))
print(preorderTraversal(S.sortedArrayToBST2(nums)))