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

Categories:

题目描述
思路分析
1. 解法一：快慢指针找中点 + 递归（推荐）
相似题目

题目描述

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

思路分析

解法一：快慢指针找中点 + 递归（推荐）

核心思路：

用快慢指针找到链表中点作为根节点。

中点左侧构建左子树，右侧构建右子树。

递归直到子链表为空。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示链表节点数。

空间复杂度：O(log n)，递归栈深度平均为树高。

// 快慢指针找中点递归建树
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // 断开左半部分
        pre.next = null;

        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

// 快慢指针找中点递归建树
func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return &TreeNode{Val: head.Val}
	}

	var pre *ListNode
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		pre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 断开左半部分
	pre.Next = nil

	root := &TreeNode{Val: slow.Val}
	root.Left = sortedListToBST(head)
	root.Right = sortedListToBST(slow.Next)
	return root
}

相似题目

题目	难度	考察点
108. 将有序数组转换为二叉搜索树	简单	递归
114. 二叉树展开为链表	中等	递归
230. 二叉搜索树中第 K 小的元素	中等	DFS
98. 验证二叉搜索树	中等	DFS
543. 二叉树的直径	简单	DFS
617. 合并二叉树	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/14733410