问题描述 链接到标题

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

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

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

示例 1:

输入: 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)$ 时间内实现随机访问，因此不能套用数组的思路。

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

代码 链接到标题 

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);
    }
};