LeetCode 第331题：验证二叉树的前序序列化

📖 文章摘要

本文详细解析LeetCode第331题“验证二叉树的前序序列化”，这是一道中等难度的二叉树和栈问题。文章提供了栈和计数两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升二叉树和栈操作能力的程序员。

核心知识点： 二叉树、栈、前序遍历、入度出度
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升二叉树操作能力的程序员

题目描述

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

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

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

示例

示例 1：

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

示例1

示例 2：

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

示例 3：

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

提示

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

解题思路

方法一：栈方法

使用栈来模拟树的构建过程。

关键点：

使用栈存储节点状态
处理空节点和非空节点
合并满足条件的节点
验证最终状态

具体步骤：

将序列按逗号分割
遍历每个节点
处理当前节点并更新栈状态
检查最终栈的状态

时间复杂度：O(n) 空间复杂度：O(n)

方法二：计数法（入度出度）

利用树的入度和出度性质。

关键点：

非空节点提供2个出度和1个入度
空节点提供0个出度和1个入度
除根节点外每个节点都需要1个入度
总入度等于总出度

具体步骤：

初始化差值diff（出度减入度）为1
遍历序列，更新差值
检查过程中差值是否合法
验证最终差值是否为0

时间复杂度：O(n) 空间复杂度：O(1)

图解思路

栈方法过程分析表

当前节点	栈状态	操作	说明
9	[9]	入栈	非空节点入栈
3	[9,3]	入栈	非空节点入栈
4	[9,3,4]	入栈	非空节点入栈
#	[9,3,4,#]	入栈	空节点入栈
#	[9,3]	合并	合并完整子树

计数法示意图

节点类型  入度  出度  差值变化
非空节点   1     2    +1
空节点     1     0    -1
最终要求：差值 = 0

代码实现

C# 实现

public class Solution {
    // 方法一：栈方法
    public bool IsValidSerialization(string preorder) {
        Stack<string> stack = new Stack<string>();
        string[] nodes = preorder.Split(',');
        
        foreach (string node in nodes) {
            while (node == "#" && stack.Count > 0 && stack.Peek() == "#") {
                stack.Pop(); // 弹出一个#
                if (stack.Count == 0) return false;
                stack.Pop(); // 弹出一个数字
            }
            stack.Push(node);
        }
        
        return stack.Count == 1 && stack.Peek() == "#";
    }
    
    // 方法二：计数法
    public bool IsValidSerializationCount(string preorder) {
        int diff = 1; // 初始差值为1（根节点）
        string[] nodes = preorder.Split(',');
        
        foreach (string node in nodes) {
            diff--; // 每个节点消耗一个入度
            if (diff < 0) return false;
            if (node != "#") {
                diff += 2; // 非空节点提供两个出度
            }
        }
        
        return diff == 0;
    }
}

Python 实现

class Solution:
    # 方法一：栈方法
    def isValidSerialization(self, preorder: str) -> bool:
        stack = []
        nodes = preorder.split(',')
        
        for node in nodes:
            while node == '#' and stack and stack[-1] == '#':
                stack.pop() # 弹出一个#
                if not stack: return False
                stack.pop() # 弹出一个数字
            stack.append(node)
        
        return len(stack) == 1 and stack[-1] == '#'
    
    # 方法二：计数法
    def isValidSerializationCount(self, preorder: str) -> bool:
        diff = 1 # 初始差值为1（根节点）
        nodes = preorder.split(',')
        
        for node in nodes:
            diff -= 1 # 每个节点消耗一个入度
            if diff < 0: return False
            if node != '#':
                diff += 2 # 非空节点提供两个出度
        
        return diff == 0

C++ 实现

class Solution {
public:
    // 方法一：栈方法
    bool isValidSerialization(string preorder) {
        vector<string> stack;
        stringstream ss(preorder);
        string node;
        
        while (getline(ss, node, ',')) {
            while (node == "#" && !stack.empty() && stack.back() == "#") {
                stack.pop_back(); // 弹出一个#
                if (stack.empty()) return false;
                stack.pop_back(); // 弹出一个数字
            }
            stack.push_back(node);
        }
        
        return stack.size() == 1 && stack.back() == "#";
    }
    
    // 方法二：计数法
    bool isValidSerializationCount(string preorder) {
        int diff = 1; // 初始差值为1（根节点）
        stringstream ss(preorder);
        string node;
        
        while (getline(ss, node, ',')) {
            diff--; // 每个节点消耗一个入度
            if (diff < 0) return false;
            if (node != "#") {
                diff += 2; // 非空节点提供两个出度
            }
        }
        
        return diff == 0;
    }
};

执行结果

C# 实现

执行用时：76 ms
内存消耗：36.8 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：0 ms
内存消耗：6.8 MB

性能对比

语言	执行用时	内存消耗	特点
C#	76 ms	36.8 MB	实现简洁，性能适中
Python	36 ms	15.1 MB	代码最简洁
C++	0 ms	6.8 MB	性能最优

代码亮点

🎯 两种不同的解题思路
💡 巧妙利用入度出度关系
🔍 完整的边界条件检查
🎨 代码结构清晰，易于理解

常见错误分析

🚫 没有处理空序列
🚫 栈操作顺序错误
🚫 入度出度计算错误
🚫 边界条件判断不当

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
栈方法	O(n)	O(n)	直观易懂	空间消耗大
计数法	O(n)	O(1)	空间效率高	不易理解

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第331题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：栈方法

方法二：计数法（入度出度）

图解思路

栈方法过程分析表

计数法示意图

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流