109.将有序链表转换为二叉搜索树

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

示例 1:

img

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

和108一样，区别就是在于如何找到链表的中间节点罢了，用之前的快慢指针法即可，这里的左右边界直接是头节点和null，因为是左闭右开的区间

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    // 主方法：将排序的链表转换为高度平衡的二叉搜索树
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null); // 从头节点开始构建
    }

    // 递归方法：构建二叉搜索树
    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) { // 递归终止条件，当左右节点相等时返回null
            return null;
        }
        ListNode mid = getMedian(left, right); // 获取中间节点作为当前子树的根
        TreeNode root = new TreeNode(mid.val); // 创建根节点
        root.left = buildTree(left, mid); // 递归构建左子树，范围从left到mid
        root.right = buildTree(mid.next, right); // 递归构建右子树，范围从mid的下一个节点到right
        return root; // 返回构建的树的根节点
    }

    // 方法：获取中间节点，用于作为BST的根节点
    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left; // 快指针，每次移动两步
        ListNode slow = left; // 慢指针，每次移动一步
        while (fast != right && fast.next != right) { // 快指针未到达右边界时循环
            fast = fast.next.next; // 快指针前进两步
            slow = slow.next; // 慢指针前进一步
        }
        return slow; // 慢指针指向中间节点，返回作为根节点
    }
}