What is the main idea behind verifying preorder serialization of a binary tree?

The main idea is to track available slots for nodes, incrementing for non-null nodes and decrementing for each node encountered, ensuring the final slots count is zero.

Can this problem be solved without building the binary tree?

Yes, using slot counting or a stack simulation, you can validate the serialization directly from the string without reconstructing the tree.

What should I do if I encounter consecutive '#' symbols?

Consecutive '#' symbols indicate null children; decrement slots accordingly and use stack or slot rules to detect completed subtrees or invalid sequences.

How does GhostInterview help detect common mistakes?

It simulates both slot counting and stack approaches, highlighting early negative slot counts or invalid subtree completions, preventing structural errors.

Are there variants of this problem I should be aware of?

Yes, variants include postorder serialization verification, using different null markers, or extending the pattern to n-ary trees with adjusted slot rules.

#331

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

验证二叉树的前序序列化

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 # 。例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#" ，其中 # 代表一个空节点。给定一串以逗号分…

字符串栈树二叉树

题目描述

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

注意：不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

输入: preorder = "1,#"
输出: false

示例 3:

输入: preorder = "9,#,#,1"
输出: false

提示:

1 <= preorder.length <= 10⁴
preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成

lightbulb

解题思路

方法一：栈

我们将字符串 preorder 按逗号分割成数组，然后遍历数组，如果遇到了连续两个 '#'，并且第三个元素不是 '#'，那么就将这三个元素替换成一个 '#'，这个过程一直持续到数组遍历结束。

最后，判断数组长度是否为 $1$ ，且数组唯一的元素是否为 '#' 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 preorder 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stk = []
        for c in preorder.split(","):
            stk.append(c)
            while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#":
                stk = stk[:-3]
                stk.append("#")
        return len(stk) == 1 and stk[0] == "#"

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the number of nodes in the preorder string, as each node is visited once. Space complexity is O(1) for slot counting or O(n) for stack-based simulation, depending on whether explicit stack storage is used.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can you verify the serialization without reconstructing the binary tree?
question_mark
What happens if the preorder string has extra or missing nodes?
question_mark
How do you track the number of available slots during traversal?

warning

常见陷阱

外企场景

error
Failing to handle consecutive null nodes correctly in the slot tracking method.
error
Not decrementing slots before checking for early termination, leading to false positives.
error
Attempting to reconstruct the tree unnecessarily, increasing space usage and complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Verify postorder serialization of a binary tree using a similar slot counting approach.
arrow_right_alt
Validate a binary tree serialization with different null markers, e.g., 'X' instead of '#'.
arrow_right_alt
Check serialization for n-ary trees by adjusting slot increments for variable number of children.

help

常见问题

外企场景

继续练习

#297 二叉树的序列化与反序列化 #257 二叉树的所有路径 #449 序列化和反序列化二叉搜索树