本文共 1620 字，大约阅读时间需要 5 分钟。

题目描述

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

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

示例:

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

解题思路

题目说给定的单链表是有序的，要转换为高度平衡的二叉搜索树，也就是说这个链表是树的前序遍历。

因此思路就转为：找到链表的中间节点，然后以此节点把链表一分为二，作为左右子树的范围。

使用快慢指针+递归

1. 通过快慢指针为到链表的中间节点。
2. 通过递归来构成节点的左右子树。
3. 递归结束条件是链表为空时链表只有一个元素时返回其本身，即 head;

代码

/** * Definition for singly-linked list. * public class ListNode { *     public int val; *     public ListNode next; *     public ListNode(int val=0, ListNode next=null) { *         this.val = val; *         this.next = next; *     } * } *//** * Definition for a binary tree node. * public class TreeNode { *     public int val; *     public TreeNode left; *     public TreeNode right; *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */public class Solution {    public TreeNode SortedListToBST(ListNode head) {        // 快慢指针：先找到中间节点，然后左右两边的链表作为左右子树，直到链表只有一个节点。        if(head == null || head.next == null) {            return head;        }        ListNode fast = head, slow = head, pre = null;        while(fast != null && fast.next != null) {            fast = fast.next.next;            pre = slow;            slow = slow.next;        }        TreeNode root = new TreeNode(slow.val);                pre.next = null;    // 把链表一分为二        root.left = SortedListToBST(head);        root.right = SortedListToBST(slow.next);        return root;    }}

复杂度分析

• 时间复杂度：\(O(nlogn)\)，其中 \(n\) 是链表长度。
• 空间复杂度：\(O(1)\)。