0109. Convert Sorted List to Binary Search Tree - chasel2361/leetcode GitHub Wiki

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

這題的做法跟上一題很類似，只是先把串鍊的值走一遍存起來，再用跟前一題一樣的方法來解

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        len_n = len(nums)
        if len_n == 0: return None
        root = self.getNode(0, len_n - 1, nums)
        return root
        
    def getNode(self, l, r, nums):
        if l > r: return None
        m = (r + l) // 2
        root = TreeNode(nums[m])
        root.left = self.getNode(l, m - 1, nums)
        root.right = self.getNode(m + 1, r, nums)
        return root

這樣寫的時間複雜度跟空間複雜度是 O(N)