題目描述
給定一個(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)
還可以使用快慢指針來獲得中間值
上述兩種方式都是尋找方法獲得中節(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ì)鏈表長(zhǎng)度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)注明出處。
