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

中等链表分治 + 中序遍历优化力扣原题 ↗

题目描述

输入一个单链表的头节点 head，链表中的值按升序排列。链表用数组表示，例如 [1,2,3]。

用链表中的全部节点值构造一棵二叉搜索树，要求高度平衡：每个节点左右子树的高度差不超过 1。

返回这棵树的根节点，树按层序数组表示，null 代表空位。答案不唯一时，返回任意一个合法的树即可。链表为空时返回空树。

示例 1

输入：head = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

解释：根为 0，左子树为 -3 带左孩子 -10，右子树为 9 带左孩子 5，各节点左右高度差都不超过 1。

示例 2

输入：head = []
输出：[]

解释：空链表对应空树。

数据范围

链表节点数在 [0, 2 * 10^4] 之间。
-10^5 <= Node.val <= 10^5

解题思路：分治 + 中序遍历优化

二叉搜索树的中序遍历正好是升序序列，也就是链表的顺序。先数出节点数 n，再按中序递归 build(lo, hi)：取中点 mid，先建左子树 [lo, mid-1]，这时链表指针 node 恰好走到第 mid 个节点，用它的值建根，指针后移一位，再建右子树 [mid+1, hi]。这样不用把链表拷贝成数组，也不用每次找中点，链表只顺序读一遍。

为什么正确

调用 build(lo, hi) 时，node 指向链表中第 lo 个节点；返回时 node 指向第 hi+1 个节点，且返回的子树恰好由第 lo..hi 个值组成。

复杂度分析

时间 O(n)：数长度一遍，建树时每个节点访问一次；空间 O(log n)，为递归栈深度（树是平衡的）。

易错点

先建左子树、再读 node 的顺序不能颠倒：如果先用 node 建根，取到的是第 lo 个值而不是第 mid 个，树就不再是二叉搜索树。另外 node 在递归中被修改，Python 里要用 nonlocal（或放在 self 上），否则内层函数只会改到局部变量。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def sortedListToBST(self, head):
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        node = head
        def build(lo, hi):
            nonlocal node
            if lo > hi:
                return None
            mid = (lo + hi + 1) // 2
            left = build(lo, mid - 1)
            root = TreeNode(node.val)
            node = node.next
            root.left = left
            root.right = build(mid + 1, hi)
            return root
        return build(0, n - 1)

class Solution {
    private ListNode node;

    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        node = head;
        return build(0, n - 1);
    }

    private TreeNode build(int lo, int hi) {
        if (lo > hi)
            return null;
        int mid = (lo + hi + 1) / 2;
        TreeNode left = build(lo, mid - 1);
        TreeNode root = new TreeNode(node.val);
        node = node.next;
        root.left = left;
        root.right = build(mid + 1, hi);
        return root;
    }
}

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int n = 0;
        ListNode* cur = head;
        while (cur) {
            n++;
            cur = cur->next;
        }
        ListNode* node = head;
        function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
            if (lo > hi)
                return nullptr;
            int mid = (lo + hi + 1) / 2;
            TreeNode* left = build(lo, mid - 1);
            TreeNode* root = new TreeNode(node->val);
            node = node->next;
            root->left = left;
            root->right = build(mid + 1, hi);
            return root;
        };
        return build(0, n - 1);
    }
};

func sortedListToBST(head *ListNode) *TreeNode {
	n := 0
	cur := head
	for cur != nil {
		n++
		cur = cur.Next
	}
	node := head
	var build func(lo, hi int) *TreeNode
	build = func(lo, hi int) *TreeNode {
		if lo > hi {
			return nil
		}
		mid := (lo + hi + 1) / 2
		left := build(lo, mid-1)
		root := &TreeNode{Val: node.Val}
		node = node.Next
		root.Left = left
		root.Right = build(mid+1, hi)
		return root
	}
	return build(0, n-1)
}

var sortedListToBST = function(head) {
    let n = 0;
    let cur = head;
    while (cur) {
        n++;
        cur = cur.next;
    }
    let node = head;
    const build = (lo, hi) => {
        if (lo > hi)
            return null;
        const mid = (lo + hi + 1) >> 1;
        const left = build(lo, mid - 1);
        const root = new TreeNode(node.val);
        node = node.next;
        root.left = left;
        root.right = build(mid + 1, hi);
        return root;
    };
    return build(0, n - 1);
};

function sortedListToBST(head: ListNode | null): TreeNode | null {
    let n = 0;
    let cur = head;
    while (cur) {
        n++;
        cur = cur.next;
    }
    let node = head;
    const build = (lo: number, hi: number): TreeNode | null => {
        if (lo > hi)
            return null;
        const mid = (lo + hi + 1) >> 1;
        const left = build(lo, mid - 1);
        const root = new TreeNode(node!.val);
        node = node!.next;
        root.left = left;
        root.right = build(mid + 1, hi);
        return root;
    };
    return build(0, n - 1);
};

载入编辑器，自己跑一遍 →

其他解法

快慢指针每层重新找中点，写法直观但是 O(n log n)；中序遍历优化先数长度，再按中序顺序依次消耗链表节点，做到 O(n)。

解法 2：分治 + 快慢指针时间 O(n log n)，空间 O(log n)

用左闭右开区间 [left, right) 表示一段链表。快指针每次走两步、慢指针走一步，快指针到达 right 时慢指针就是中位数节点。以它为根，递归构造 [left, mid) 和 [mid.next, right)。

思路和有序数组版本一致，最容易想到。每层递归都要重新扫描链表找中点，总时间多一个 log n。

class Solution:
    def sortedListToBST(self, head):
        def build(left, right):
            if left is right:
                return None
            slow = fast = left
            while fast is not right and fast.next is not right:
                fast = fast.next.next
                slow = slow.next
            root = TreeNode(slow.val)
            root.left = build(left, slow)
            root.right = build(slow.next, right)
            return root
        return build(head, None)

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return build(head, null);
    }

    private TreeNode build(ListNode left, ListNode right) {
        if (left == right) return null;
        ListNode slow = left, fast = left;
        while (fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = build(left, slow);
        root.right = build(slow.next, right);
        return root;
    }
}

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, nullptr);
    }

    TreeNode* build(ListNode* left, ListNode* right) {
        if (left == right) return nullptr;
        ListNode* slow = left;
        ListNode* fast = left;
        while (fast != right && fast->next != right) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode* root = new TreeNode(slow->val);
        root->left = build(left, slow);
        root->right = build(slow->next, right);
        return root;
    }
};

func sortedListToBST(head *ListNode) *TreeNode {
	var build func(left, right *ListNode) *TreeNode
	build = func(left, right *ListNode) *TreeNode {
		if left == right {
			return nil
		}
		slow, fast := left, left
		for fast != right && fast.Next != right {
			fast = fast.Next.Next
			slow = slow.Next
		}
		root := &TreeNode{Val: slow.Val}
		root.Left = build(left, slow)
		root.Right = build(slow.Next, right)
		return root
	}
	return build(head, nil)
}

var sortedListToBST = function(head) {
    const build = (left, right) => {
        if (left === right) return null;
        let slow = left, fast = left;
        while (fast !== right && fast.next !== right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        const root = new TreeNode(slow.val);
        root.left = build(left, slow);
        root.right = build(slow.next, right);
        return root;
    };
    return build(head, null);
};

function sortedListToBST(head: ListNode | null): TreeNode | null {
    const build = (left: ListNode | null, right: ListNode | null): TreeNode | null => {
        if (left === right) return null;
        let slow = left!, fast: ListNode | null = left;
        while (fast !== right && fast!.next !== right) {
            fast = fast!.next!.next;
            slow = slow.next!;
        }
        const root = new TreeNode(slow.val);
        root.left = build(left, slow);
        root.right = build(slow.next, right);
        return root;
    };
    return build(head, null);
};

链表专题的其他题目

查看链表全部题目 →