題目描述

給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。

本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1。

示例:

給定的有序鏈表： [-10, -3, 0, 5, 9],

一個(gè)可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個(gè)高度平衡二叉搜索樹：

      0
     / \
   -3   9
   /   /
 -10  5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路

# 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:
        # 首先轉(zhuǎn)成數(shù)組,就可以按照索引來快速獲取中間值
        arr = []
        result = []

        while head is not None:
            arr.append(head.val)
            head = head.next
        def sortedArryToBST(arr):
            if len(arr)==0:
                return None
            if len(arr) == 1:
                return TreeNode(arr[0])
            mid = (len(arr))//2 
            root = TreeNode(arr[mid])
            root.left = sortedArryToBST(arr[:mid])
            root.right = sortedArryToBST(arr[mid+1:])
            return root
        return sortedArryToBST(arr)
        

圖片.png

還可以使用快慢指針來獲得中間值

d072de5dd5b0ff86df59ff948b5f1b2.jpg

上述兩種方式都是尋找方法獲得中節(jié)點(diǎn) 用中間節(jié)點(diǎn)構(gòu)建root，導(dǎo)致我們每次構(gòu)建樹節(jié)點(diǎn)得時(shí)候都要尋找中間節(jié)點(diǎn)
能不能不尋找中間節(jié)點(diǎn)，而是令建立節(jié)點(diǎn)的順序 匹配 鏈表元素順序？這樣每次建立節(jié)點(diǎn)時(shí)，只需要獲取鏈表下一個(gè)元素即可。方法如下：

• 使用遞歸模擬中序遍歷過程，建立節(jié)點(diǎn)的順序即與鏈表元素順序一一對(duì)應(yīng)，bottom-up建立樹，最終返回根節(jié)點(diǎn)。遞歸調(diào)用得最底層一個(gè)節(jié)點(diǎn)得左兒子是空，右兒子也是空，只有父節(jié)點(diǎn)是鏈表得head.val。
• 遞歸前需要統(tǒng)計(jì)鏈表長度n，整體算法復(fù)雜度O(N)。

作者：jyd
鏈接：https://leetcode-cn.com/problems/two-sum/solution/convert-sorted-list-to-binary-search-tree-di-ding-/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

class Solution:
    def __init__(self):
        self.head = None
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        n, self.head = 0, head
        while head:
            head = head.next
            n += 1
        return self.to_bst(0, n - 1)
    def to_bst(self, left, right):
        if left > right: return
        m = (left + right) // 2
        left_child = self.to_bst(left, m - 1)
        father = TreeNode(self.head.val)
        self.head = self.head.next
        father.left = left_child
        father.right = self.to_bst(m + 1, right)
        return father

作者：jyd
鏈接：https://leetcode-cn.com/problems/two-sum/solution/convert-sorted-list-to-binary-search-tree-di-ding-/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。