leetcode 108. Convert Sorted Array to Binary Search Tree(python)

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

描述

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

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: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

Note:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order.

解析

根據題意,就是給出了一個整數列表 nums ,其中的元素都是已經經過升序排序的列表。題目要求我們將 nums 中的整數轉換成一棵高度平衡的二叉搜尋樹,返回其根節點。

高度平衡二叉樹是一種特殊二叉樹,其中每個節點的兩個子樹的深度相差不超過 1。

思路很簡單,之前提到了很多次,直接使用遞迴解決就行了,只不過要結合題意設計一下結構。這裡要把已經排序的列表 nums 轉換成一棵高度平衡二叉樹,關鍵在於先找出根節點,所以只需要將 nums[MID] 的值作為根節點,然後對 nums[:MID] 進行左子樹的遞迴,對 nums[MID+1:] 進行右子樹的遞迴,即可得到符合題意的高度平衡二叉樹。

解答

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[int]
        :rtype: TreeNode
        """
        if not nums:return None
        MID = len(nums)//2
        root = TreeNode(nums[MID])
        root.left = self.sortedArrayToBST(nums[:MID])
        root.right = self.sortedArrayToBST(nums[MID+1:])
        return root

執行結果

Runtime: 97 ms, faster than 32.83% of Python online submissions for Convert Sorted Array to Binary Search Tree.
Memory Usage: 16 MB, less than 92.78% of Python online submissions for Convert Sorted Array to Binary Search Tree.

原題連結:https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

您的支援是我最大的動力