本文共 2208 字，大约阅读时间需要 7 分钟。

为了验证给定的前序序列是否是正确的二叉树序列化，可以使用栈来跟踪每个节点的子节点数量。以下是详细的步骤和代码实现。

样例分析

示例1： 输入序列为“9,3,4,#,#,1,#,#,2,#,6,#,#”。

• 栈初始为 [1]。
• 遇到9：弹出1，减到0，将2入栈，栈为 [2]。
• 遇到3：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到4：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到1：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到2：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到6：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为空，返回true。

示例2： 输入序列为“1,#”。

• 栈初始为 [1]。
• 遇到1：弹出1，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为空，返回false。

示例3： 输入序列为“9,#,#,1”。

• 栈初始为 [1]。
• 遇到9：弹出1，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到1：弹出2，减到1，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为 [2]。
• 遇到#：弹出2，减到0，将2入栈，栈为空，返回false。

栈方法详解

初始化： 栈中最初放入一个1，表示根节点尚未处理。

遍历每个节点：

错误条件：

• 遇到错误的节点（如两连#）。
• 栈为空时处理节点。
• 栈顶元素在处理过程中出现负值。

代码实现

C++代码：

#include 
   
    
#include 
    
     
using namespace std;
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stack
     
       childNodes;
        childNodes.push(1);
        int len = preorder.length();
        for(int i = 0; i < len; ++i) {
            char ch = preorder[i];
            if (ch > '0' && ch < '9') {
                if (i == len - 1 || preorder[i+1] == ',') {
                    if (childNodes.empty()) return false;
                    if (--childNodes.top() == 0) childNodes.pop();
                    childNodes.push(2);
                }
            } else if (ch == '#') {
                if (childNodes.empty()) return false;
                if (--childNodes.top() == 0) childNodes.pop();
            }
        }
        return childNodes.empty();
    }
};
     
    
   

Python代码：

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

总结

通过上述方法，可以有效地验证给定的前序序列是否是正确的二叉树序列化。栈的使用帮助跟踪每个节点的子节点数量，确保序列符合二叉树的结构要求。