# \[109]\[中等]\[DFS]\[双指针] 有序链表转换二叉搜索树

## 题目描述

[109. 有序链表转换二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/)

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

```
给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
```

## 解题思路

### 转成数组

一个直接的思路就是先将整个列表过一遍, 将每个节点的值取出来组成一个**递增**的数组, 这样问题就转换成了 [108. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/). 实际上这种方法的效率也是比较高的. 解法如下:

```python
# 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:
        nums = []
        current = head
        while current is not None:
            nums.append(current.val)
            current = current.next

        n = len(nums)

        def get_root(l, r):
            if l > r:
                return None

            mid = (l + r) // 2
            root = TreeNode(nums[mid])
            root.left = get_root(l, mid - 1)
            root.right = get_root(mid + 1, r)
            return root
        return get_root(0, n - 1)
```

### 快慢指针(双指针)

如果不转成数组, 只是用链表的方法, 我们仍然要找到中间节点. 常常使用**双指针**, 一快一慢, **快慢指针**配合找到中间节点. 分别定义为`slow_ptr`和`fast_ptr`, `slow_ptr`每次移动一个结点, `fast_ptr`每次移动两个结点, 这样当`fast_ptr`移动到链表的截尾时, `slow_ptr`正好访问到中间节点, 无论链表的长度奇偶.

仍然使用**递归**方法, 找到中间节点后, 将中间节点的前后断开, 然后前后子链再递归地使用同样的方法找到中间节点. 为了找到中间节点, 即`slow_ptr`, 再使用一个指针`prev_ptr`, 记录`slow_ptr`前一个元素.

具体内容参考:

[有序链表转换二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-by-/)

```python
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def get_root(pointer):
            if pointer is None:
                return None
            if pointer.next is None:
                return TreeNode(pointer.val)

            fast, slow, pre = pointer, pointer, None
            while fast is not None and fast.next is not None:
                fast = fast.next.next
                pre = slow
                slow = slow.next

            root = TreeNode(slow.val)
            pre.next = None  # 切断左子链与后面的连接, 进入递归
            root.left = get_root(pointer)
            root.right = get_root(slow.next)
            return root
        return get_root(head)
```

## 相关题目

* 数组版: [108. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/shu/109-you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.