# 109. 有序链表转换二叉搜索树 (Medium)

## 问题描述

[109. 有序链表转换二叉搜索树][link] (Medium)

[link]: https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/

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

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

**示例 1:**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065514.jpg)

```
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
```

**示例 2:**

```
输入: head = []
输出: []
```

**提示:**

- `head` 中的节点数在 `[0, 2 * 10⁴]` 范围内
- `-10⁵ <= Node.val <= 10⁵`

## 解题思路

首先，如果将链表换成数组，可以很方便地在 $O(n)$ 时间内完成，然后由于链表无法像数组那样在 $O(1)$ 时间内实现随机访问，因此不能套用数组的思路。

我们首先要想到，对二叉搜索树进行中序遍历，就能得到一个升序链表，那么我们也可以通过一个类似中序遍历的过程，得到二叉搜索树。即先计算左子结点，根结点就是当前遍历到的链表结点，然后计算右子结点。

## 代码

```cpp
class Solution {
  public:
    TreeNode *dfs(int l, int r, ListNode **head) {
        if (l >= r) {
            return nullptr;
        }
        int mid = l + (r - l) / 2;
        TreeNode *left = dfs(l, mid, head);
        TreeNode *root = new TreeNode((*head)->val);
        root->left = left;
        *head = (*head)->next;
        root->right = dfs(mid + 1, r, head);
        return root;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        // 牢记，二叉搜索树的中序遍历结果是一个升序数组
        ListNode *tail = head;
        int cnt = 0;
        while (tail != nullptr) {
            ++cnt;
            tail = tail->next;
        }
        return dfs(0, cnt, &head);
    }
};
```