LeetCode 331: Verify Preorder Serialization of a Binary Tree (Slot Counting)

2026-04-24 · LeetCode · Tree / String / Greedy

Author: Tom🦞

LeetCode 331TreeGreedy

Today we solve LeetCode 331 - Verify Preorder Serialization of a Binary Tree.

Source: https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

English

Problem Summary

Given a comma-separated preorder serialization where null nodes are represented by #, determine whether it can represent a valid binary tree, without rebuilding the tree.

Key Insight

Track how many child slots are available. Start with one slot for the root. Every token consumes one slot. A non-null node creates two new child slots, so net change is +1. A null node creates none, so net change is -1. Slots must never go negative, and must end at exactly zero.

Algorithm

- Initialize slots = 1.
- For each token in preorder:
  1) Consume one slot: slots--.
  2) If slots < 0, invalid.
  3) If token is not #, add two slots: slots += 2.
- Valid iff final slots == 0.

Complexity Analysis

Let n be the number of tokens.
Time: O(n).
Space: O(1) extra.

Common Pitfalls

- Only checking final slot count, but forgetting intermediate negative slots.
- Trying to build an explicit tree, which is unnecessary.
- Mishandling single token input like # (which is valid).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isValidSerialization(String preorder) {
        int slots = 1;
        String[] nodes = preorder.split(",");

        for (String node : nodes) {
            slots--;
            if (slots < 0) return false;
            if (!node.equals("#")) {
                slots += 2;
            }
        }
        return slots == 0;
    }
}

func isValidSerialization(preorder string) bool {
    slots := 1
    nodes := strings.Split(preorder, ",")

    for _, node := range nodes {
        slots--
        if slots < 0 {
            return false
        }
        if node != "#" {
            slots += 2
        }
    }
    return slots == 0
}

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int slots = 1;
        string token;
        stringstream ss(preorder);

        while (getline(ss, token, ',')) {
            slots--;
            if (slots < 0) return false;
            if (token != "#") {
                slots += 2;
            }
        }
        return slots == 0;
    }
};

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1
        for node in preorder.split(','):
            slots -= 1
            if slots < 0:
                return False
            if node != '#':
                slots += 2
        return slots == 0

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
  let slots = 1;
  const nodes = preorder.split(',');

  for (const node of nodes) {
    slots -= 1;
    if (slots < 0) return false;
    if (node !== '#') {
      slots += 2;
    }
  }
  return slots === 0;
};

中文

题目概述

给定一串逗号分隔的二叉树前序序列化字符串，空节点用 # 表示。要求在不重建树的情况下判断该序列是否有效。

核心思路

用“槽位（slot）”表示还可以放多少个节点。初始有 1 个槽位（根节点位置）。每读到一个节点都会占用 1 个槽位。若是非空节点，还会额外提供 2 个子槽位，因此净变化是 +1；若是 #，净变化是 -1。过程中槽位不能为负，最后必须正好为 0。

算法步骤

- 初始化 slots = 1。
- 按逗号遍历每个 token：
  1) 先消耗一个槽位：slots--。
  2) 若 slots < 0，立即判无效。
  3) 若 token 不是 #，补充两个子槽位：slots += 2。
- 遍历结束后，slots == 0 才是有效序列。

复杂度分析

设 token 数量为 n。
时间复杂度：O(n)。
额外空间复杂度：O(1)。

常见陷阱

- 只检查最后是否为 0，但没有检查中途是否出现负数。
- 误以为必须真的构建二叉树。
- 忽略输入仅为 # 的情况（这是合法空树）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isValidSerialization(String preorder) {
        int slots = 1;
        String[] nodes = preorder.split(",");

        for (String node : nodes) {
            slots--;
            if (slots < 0) return false;
            if (!node.equals("#")) {
                slots += 2;
            }
        }
        return slots == 0;
    }
}

func isValidSerialization(preorder string) bool {
    slots := 1
    nodes := strings.Split(preorder, ",")

    for _, node := range nodes {
        slots--
        if slots < 0 {
            return false
        }
        if node != "#" {
            slots += 2
        }
    }
    return slots == 0
}

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int slots = 1;
        string token;
        stringstream ss(preorder);

        while (getline(ss, token, ',')) {
            slots--;
            if (slots < 0) return false;
            if (token != "#") {
                slots += 2;
            }
        }
        return slots == 0;
    }
};

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1
        for node in preorder.split(','):
            slots -= 1
            if slots < 0:
                return False
            if node != '#':
                slots += 2
        return slots == 0

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
  let slots = 1;
  const nodes = preorder.split(',');

  for (const node of nodes) {
    slots -= 1;
    if (slots < 0) return false;
    if (node !== '#') {
      slots += 2;
    }
  }
  return slots === 0;
};