109. 有序鏈表轉(zhuǎn)換二叉搜索樹

題目

先將鏈表轉(zhuǎn)換為數(shù)組，再利用數(shù)組來構(gòu)建高度平衡二叉樹。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:

        def dg(lp,rp):
            if lp>rp:
                return None
            mid = (lp+rp)//2
            node = TreeNode(nums[mid])
            node.left = dg(lp,mid-1)
            node.right = dg(mid+1,rp)
            return node

        nums = []
        p = head
        while p:
            nums.append(p.val)
            p = p.next
       
        return dg(0,len(nums)-1)