LeetCode 426. 将二叉搜索树转化为排序的双向链表

2025-04-28 HGNULB 约 5 分钟

文章信息 13 个分类 7 个标签

分类

LeetCode CodeTop 中等未解决会员题 10-20 腾讯字节微软拼多多网易快手猿辅导

题目描述

✅ 426. 将二叉搜索树转化为排序的双向链表

题意分析

将二叉搜索树的原有节点改连成有序循环双向链表，并返回最小值节点。原来的 left 改为指向前驱，right 改为指向后继；最小节点的前驱是最大节点，最大节点的后继是最小节点。

这里的原地转换是复用节点并修改指针，不新建另一份链表。既要保证节点升序，也要把两个方向和首尾环都连接完整。

解法：中序遍历原地双向连接

核心思路

[!blue]

二叉搜索树的中序遍历顺序就是节点的升序顺序，因此在“左子树 → 当前节点 → 右子树”的访问过程中直接连接相邻节点即可，不需要额外排序。

用 head 保存第一个访问的节点，用 pre 保存最近访问的节点。访问 node 时，已经处理的节点构成一段升序链表，pre 是它的尾部：若 pre 为空，说明 node 是最小节点，记录为 head；否则设置 pre.right = node 和 node.left = pre，把当前节点接到末尾。随后令 pre = node。

指针修改必须放在左子树遍历结束之后，此时 node.left 不再需要作为左子树入口。连接时只修改前驱的 right，不修改当前节点的 right，因此接下来仍能通过 dfs(node.right) 进入原右子树。已经进入的递归调用保留了节点引用，也不会因前驱改连而丢失遍历位置。

所有节点处理完后，head 是最小节点，pre 是最大节点，再设置 head.left = pre、pre.right = head 完成闭环。闭环放在最后，避免遍历过程中沿新链表重新走回已访问节点。

解题步骤

初始化本次调用的 head、pre；空树直接返回空。

dfs(node) 遇到空节点时结束，否则先递归遍历左子树。

若 pre 为空，记录 head = node；否则把 pre 与 node 双向相连。

更新 pre = node，再递归遍历右子树。

根节点的遍历完成后，把头尾双向相连，返回 head。单节点时 head 与 pre 相同，两条指针自然都指向自己。

代码实现

class Solution {
    private Node head;
    private Node pre;

    public Node treeToDoublyList(Node root) {
        // 入口重置本次遍历状态，避免与前一次调用的链表相连。
        head = null;
        pre = null;

        if (root == null) {
            return null;
        }

        dfs(root);
        // 整次中序遍历结束后才闭环，防止破坏未遍历的子树。
        head.left = pre;
        pre.right = head;

        return head;
    }

    private void dfs(Node node) {
        if (node == null) {
            return;
        }

        dfs(node.left);

        if (pre == null) {
            head = node;
        } else {
            pre.right = node;
            node.left = pre;
        }

        pre = node;
        dfs(node.right);
    }
}

func treeToDoublyList(root *Node) *Node {
    if root == nil {
        return nil
    }

    var head *Node
    var pre *Node
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }

        dfs(node.Left)
        if pre == nil {
            head = node
        } else {
            // 当前节点与中序前驱双向连接，原右子树仍留给后续遍历。
            pre.Right = node
            node.Left = pre
        }
        pre = node
        dfs(node.Right)
    }

    dfs(root)
    // 整次中序遍历结束后才闭环，防止破坏未遍历的子树。
    head.Left = pre
    pre.Right = head
    return head
}

复杂度分析

时间复杂度：$O(n)$，每个节点恰好访问并连接一次。

空间复杂度：$O(h)$，$h$ 为树高，开销来自递归栈；平衡树为 $O(\log n)$，退化树为 $O(n)$。

关键点总结

[!green]

中序遍历提供升序，pre 把相邻访问顺序转成双向指针关系。

先完成左子树，再改当前节点的左指针，并保留原右子树入口供后续递归。

所有相邻节点连接完成后，最后只需补上最小值与最大值之间的两条连接。

复用原节点不代表额外空间是常数，递归仍需 $O(h)$ 的调用栈。

易错点总结

[!yellow]

访问点必须位于左右子树递归之间；先序或后序连接都不能保证升序。

每对相邻节点要同时修改两个方向，只改 pre.right 会让反向指针仍指向原树结构。

空树不能执行头尾连接；非空树不能漏掉闭环，否则返回的只是普通双向链表。

Java 的 head、pre 是成员变量，每次入口都要重置，避免同一个 Solution 实例处理新树时沿用上次状态。Go 的变量在函数内声明，每次调用都会重新初始化。

相似题目

题目	难度	关联与区别
897. 递增顺序搜索树	简单	同样按BST中序重连节点，原题只连递增右链，本题还要连接前驱及首尾成环。
114. 二叉树展开为链表	中等	同样原地重连树节点，原题按前序展开普通二叉树，本题按中序生成有序双向链。
补充题 195. 二叉搜索树转非循环双向链表	中等	都在中序遍历时连接当前节点与前驱；本题首尾相连，补充题保持两端不相连。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/23850954

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！