LeetCode 1028. 从先序遍历还原二叉树

2026-09-13 HGNULB 约 5 分钟

文章信息 2 个分类 4 个标签

分类

LeetCode 困难

题目描述

✅ 1028. 从先序遍历还原二叉树

题意分析

字符串按前序顺序记录二叉树节点，每个节点先用连续连字符表示深度，再写节点的正整数值。根深度为 0，单孩子节点保证只有左孩子，要求还原原树。连字符是深度标记，不是负号；输入保证是合法编码，TreeNode 由平台提供。

解法：解析深度并维护祖先栈

核心思路

[!blue]

前序顺序是根、左子树、右子树，读到一个新节点时，它的父节点一定已经出现。深度为 depth 的节点，其父亲必须位于深度 depth - 1，因此需要保留最近访问路径上的祖先，而不是只记住上一个节点。

栈中从下标 0 开始依次保存根到最近节点的路径，下标恰好等于节点深度。读到新节点后，将栈缩到长度 depth：深度大于等于它的旧节点都不是它的父亲，应从路径中移除；剩余栈顶便是深度 depth - 1 的父节点。若新节点是上一节点的孩子，栈长原本就等于它的深度，不需要弹出。

找到父节点后，若父节点还没有左孩子，就先接到左侧；否则接到右侧。前序顺序保证左子树先出现，而“只有一个孩子时必须是左孩子”的条件消除了单孩子方向的歧义。根没有父亲，只需压栈；每个新节点连接后再入栈，路径不变量便恢复。

解析使用同一个文本游标：先数完整的连字符段，再逐位累积后续整数，不能把多位数拆成多个节点。合法编码保证每段连字符后都跟着数字，节点深度也不会跳过一个不存在的父节点。

解题步骤

初始化空祖先栈和文本游标，逐个读取节点的深度与完整数值。

Java 弹出多余节点，Go 直接截取到 stack[:depth]，使栈只保留当前节点的祖先。

创建节点；若栈非空，将它接为栈顶节点的第一个左孩子或后续右孩子。

将新节点压栈，继续读取，直到文本全部消费完。

返回栈底的根。只有根节点时也经过同一流程，根始终保留在路径底部。

代码实现

class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        List<TreeNode> stack = new ArrayList<>();
        int index = 0;

        while (index < traversal.length()) {
            int depth = 0;
            int value = 0;

            while (traversal.charAt(index) == '-') {
                depth++;
                index++;
            }

            while (index < traversal.length() && Character.isDigit(traversal.charAt(index))) {
                value = value * 10 + traversal.charAt(index++) - '0';
            }

            while (stack.size() > depth) {
                stack.remove(stack.size() - 1);
            }

            TreeNode node = new TreeNode(value);

            if (!stack.isEmpty()) {
                TreeNode parent = stack.get(stack.size() - 1);

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

            stack.add(node);
        }

        return stack.get(0);
    }
}

func recoverFromPreorder(traversal string) *TreeNode {
    stack := []*TreeNode{
    }
    for index := 0; index < len(traversal); {
        depth, value := 0, 0
        for traversal[index] == '-' {
            depth++
            index++
        }
        for index < len(traversal) && traversal[index] >= '0' && traversal[index] <= '9' {
            value = value*10 + int(traversal[index]-'0')
            index++
        }
        stack = stack[:depth]
        node := &TreeNode{Val: value}
        if len(stack) > 0 {
            parent := stack[len(stack)-1]
            if parent.Left == nil {
                parent.Left = node
            } else {
                parent.Right = node
            }
        }
        stack = append(stack, node)
    }
    return stack[0]
}

复杂度分析

设编码文本长度为 L、节点数为 n、树高为 h。

时间复杂度：$O(L)$。每个字符只解析一次，每个节点入栈一次、最多出栈一次；深树的大量连字符也包含在 L 中。

空间复杂度：祖先栈占 $O(h)$ 辅助空间，另需 $O(n)$ 空间保存新建结果树。

关键点总结

[!green]

深度决定父节点所在层级，栈保存该层仍有效的最近祖先。

前序遍历决定先左后右，单孩子必须在左侧的保证使还原结构唯一。

栈只是当前路径，弹栈不会删除已经连接好的结果树节点。

易错点总结

[!yellow]

节点值可能有多位，应把连续数字读完，再创建一个节点。

回到浅层时要移除所有深度大于等于当前深度的旧节点，不能只弹出一个。

父节点深度比当前节点少 1，截断后的栈长应等于当前深度，而不是再多保留一层。

不能把上一节点直接当父亲，跨过完整子树后，新的父亲可能是更浅的祖先。

当前解析依赖题目给出的合法编码和单左孩子保证，不能据此推断任意字符串都能唯一还原。

相似题目

题目	难度	关联与区别
105. 从前序与中序遍历序列构造二叉树	中等	同为还原二叉树：原题用中序定位子树边界，本题用显式深度确定父子关系。
297. 二叉树的序列化与反序列化	困难	对照结构编码：序列化可用空标记保留缺失孩子，本题借助单孩子在左侧的额外保证。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/30029347

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