2.9 有序鏈表轉(zhuǎn)換二叉搜索樹 1. 題目描述 給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。 本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1。 示例: 給定的有序鏈表： [-10, -3, 0, 5, 9]，一個(gè)可能的答案是：[0, -3, 9, -10, null, 5]，它可以表示下面這個(gè)高度平衡二叉搜索樹： ``` ???0 ???/ \ ??-3??9 ??/??/ ?-10?5 ``` 2. 分析與解法 解法一 ??： 我們知道二叉搜索樹的中序遍歷就是一個(gè)單調(diào)遞增的序列，那么這個(gè)問(wèn)題其實(shí)就是中序遍歷轉(zhuǎn)化為二叉搜索樹。和類似的問(wèn)題有Leetcode 105：從前序與中序遍歷序列構(gòu)造二叉樹； Leetcode 106：從中序與后序遍歷序列構(gòu)造二叉樹。一個(gè)比較容易想到的思路就是遞歸，我們可以將中間的元素mid放在root，然后將[:mid-1]放在root.left，再把[mid+1:]放在root.right。但是題設(shè)給???我們的是一個(gè)鏈表，所以我們無(wú)法快速求解出mid的位置，我們可以先將鏈表轉(zhuǎn)化成數(shù)組就可以啦。 參考代碼： ```python class Solution: ??def sortedListToBST(self, head): ????list_bst = list() ????while head: ??????list_bst.append(head.val) ??????head = head.next ????return self.convertBST(0, len(list_bst) - 1, list_bst) ??def convertBST(self, left, right, list_bst): ????if left > right: ??????return ????mid = (left + right) // 2 ????res = TreeNode(list_bst[mid]) ????res.left = self.convertBST(left, mid - 1, list_bst) ????res.right = self.convertBST(mid + 1, right, list_bst) ????return res ``` 解法二 ?? 快慢指針： 對(duì)于這種中點(diǎn)問(wèn)題一個(gè)常見的處理思路就是通過(guò)快慢指針。我們可以建立兩個(gè)指針slow和fast，其中一個(gè)slow=slow.next，另外一個(gè)fast=fast.next.next，這樣當(dāng)我們的fast指向最后節(jié)點(diǎn)的時(shí)候，slow一定是指向中間節(jié)點(diǎn)的。但是此時(shí)有一個(gè)問(wèn)題，我們此時(shí)無(wú)法知道slow的前一個(gè)位置了。怎么辦？???我們可以讓fast提前跑。具體操作如下： ```python class Solution: ??def sortedListToBST(self, head): ????if not head: ??????return ????if not head.next: ??????return TreeNode(head.val) ????slow, fast = head, head.next.next ????while fast and fast.next: ??????slow = slow.next ??????fast = fast.next.next ????tmp = slow.next ????slow.next = None ????res = TreeNode(tmp.val) ????res.left = self.sortedListToBST(head) ????res.right = self.sortedListToBST(tmp.next) ????return res ``` 解法三 ?? 遞推： 對(duì)于這個(gè)問(wèn)題，我們可以從后向前思考，可以先找到左下角的樹，然后再往上遞推。 ```python class Solution: ??def sortedListToBST(self, head): ????cur = head ????list_len = 0 ????while cur: ??????cur = cur.next ??????list_len += 1 ????self.node = head ????return self.convertBST(0, list_len - 1) ??def convertBST(self, left, right): ????if left > right: ??????return ????mid = (left + right) // 2 ????left = self.convertBST(left, mid - 1) ????res = TreeNode(self.node.val) ????res.left = left ????self.node = self.node.next ????right = self.convertBST(mid + 1, right) ????res.right = right ????return res ``` 這種寫法不容易思考，可以參考Leetcode 94:二叉樹的中序遍歷（最優(yōu)雅的解法！?。。┳詈蟮慕夥?。 ??