人工智能AI面试题-2.9 有序链表转换二叉搜索树

2.9 有序链表转换二叉搜索树 1. 题目描述 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 示例: 给定的有序链表： [-10, -3, 0, 5, 9]，一个可能的答案是：[0, -3, 9, -10, null, 5]，它可以表示下面这个高度平衡二叉搜索树： ```    0    / \   -3  9   /  /  -10 5 ``` 2. 分析与解法 解法一 🧐： 我们知道二叉搜索树的中序遍历就是一个单调递增的序列，那么这个问题其实就是中序遍历转化为二叉搜索树。和类似的问题有Leetcode 105：从前序与中序遍历序列构造二叉树； Leetcode 106：从中序与后序遍历序列构造二叉树。一个比较容易想到的思路就是递归，我们可以将中间的元素mid放在root，然后将[:mid-1]放在root.left，再把[mid+1:]放在root.right。但是题设给   我们的是一个链表，所以我们无法快速求解出mid的位置，我们可以先将链表转化成数组就可以啦。 参考代码： ```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 ``` 解法二 🚀 快慢指针： 对于这种中点问题一个常见的处理思路就是通过快慢指针。我们可以建立两个指针slow和fast，其中一个slow=slow.next，另外一个fast=fast.next.next，这样当我们的fast指向最后节点的时候，slow一定是指向中间节点的。但是此时有一个问题，我们此时无法知道slow的前一个位置了。怎么办？   我们可以让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 ``` 解法三 🧩 递推： 对于这个问题，我们可以从后向前思考，可以先找到左下角的树，然后再往上递推。 ```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:二叉树的中序遍历（最优雅的解法！！！）最后的解法。 😎