Medium

题目描述

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

示例 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^4] 范围内
  • -10^5 <= Node.val <= 10^5

解题思路

解题思路

这道题要求将有序链表转换为高度平衡的二叉搜索树，核心是找到链表的中点作为根节点。

方法一：快慢指针找中点（推荐）

使用快慢指针技巧找到链表中点，然后递归构建左右子树：

  1. 空链表直接返回 null
  2. 只有一个节点时，该节点作为根节点
  3. 使用快慢指针找到中点，中点作为根节点
  4. 将链表分为左右两部分，递归构建左右子树

关键在于正确断开链表：需要记录中点前一个节点，将其 next 设为 null。

方法二：转数组再构建

先遍历链表将所有值存入数组，然后用数组构建平衡 BST。虽然空间复杂度较高，但代码更简洁。

方法三：中序遍历

利用中序遍历的性质，先计算链表长度，然后按照中序遍历的顺序构建 BST，同时移动链表指针。这种方法只需遍历链表一次。

推荐使用方法一，它在时间和空间复杂度上都比较优秀，且思路清晰易懂。

代码实现

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);
        
        // 使用快慢指针找中点
        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 断开链表
        prev->next = nullptr;
        
        // 构建树
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        
        return root;
    }
};

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        if not head.next:
            return TreeNode(head.val)
        
        # 使用快慢指针找中点
        prev = None
        slow = head
        fast = head
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        
        # 断开链表
        prev.next = None
        
        # 构建树
        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        
        return root

public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        
        // 使用快慢指针找中点
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 断开链表
        prev.next = null;
        
        // 构建树
        TreeNode root = new TreeNode(slow.val);
        root.left = SortedListToBST(head);
        root.right = SortedListToBST(slow.next);
        
        return root;
    }
}

var sortedListToBST = function(head) {
    if (!head) return null;
    if (!head.next) return new TreeNode(head.val);
    
    // 使用快慢指针找中点
    let prev = null;
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 断开链表
    prev.next = null;
    
    // 构建树
    const root = new TreeNode(slow.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度快慢指针法数组转换法中序遍历法
时间复杂度O(n log n)O(n)O(n)
空间复杂度O(log n)O(n)O(log n)

说明：

  • 快慢指针法：每次递归都需要 O(n) 时间找中点，递归深度 O(log n)
  • 数组转换法：需要 O(n) 额外空间存储数组
  • 中序遍历法：时间最优但实现较复杂

相关题目