LeetCode 331. 验证二叉树的前序序列化

Categories:

题目描述
思路分析
1. 解法一：槽位计数（推荐）
相似题目

题目描述

✅ 331. 验证二叉树的前序序列化

思路分析

解法一：槽位计数（推荐）

核心思路：

初始有 1 个槽位，读一个节点就消耗 1 个槽位。

非空节点会新增 2 个槽位，空节点不新增。

过程中槽位不能为负，结束时槽位必须为 0。

复杂度分析：

时间复杂度：O(n)，其中 n 表示序列长度。

空间复杂度：O(1)，仅使用常数额外空间。

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

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

        return slots == 0;
    }
}

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

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

	return slots == 0
}

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	序列化
449. 序列化和反序列化二叉搜索树	中等	序列化
105. 从前序与中序遍历序列构造二叉树	中等	递归
1008. 前序遍历构造二叉搜索树	中等	递归
331. 验证二叉树的前序序列化	中等	槽位计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/50533951