1.题目基本信息

1.1.题目描述

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

1.2.题目地址

https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/

2.解题方法

2.1.解题思路

计数。定义“槽位”为“当前二叉树等待被填充的位置”；当遍历到#，即空节点时，消耗一个槽位；当遍历到数字时，消耗一个槽位，增加两个槽位；如果最终槽位为0，即刚好完全填充，则表示是合法的前序序列

3.解题代码

python代码 计数

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # 思路：计数。定义“槽位”为“当前二叉树等待被填充的位置”；当遍历到#，即空节点时，消耗一个槽位；当遍历到数字时，消耗一个槽位，增加两个槽位；如果最终槽位为0，即刚好完全填充，则表示是合法的前序序列
        slots = 1
        n = len(preorder)
        i = 0
        while i < n:
            if slots == 0:
                return False
            if preorder[i] == ",":
                i += 1
                continue
            elif preorder[i] == "#":
                slots -= 1
                i += 1
            else:
                # 读取一个数字
                numStr = ""
                while i < n and preorder[i].isdigit():
                    numStr += preorder[i]
                    i += 1
                slots += 1
        return slots == 0

python代码 栈

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # 思路：栈
        stack = [1] # 初始化认为是root结点需要用的槽位
        n = len(preorder)
        i = 0
        while i < n:
            if not stack:
                return False
            if preorder[i] == ",":
                i += 1
                continue
            elif preorder[i] == "#":
                stack[-1] -= 1
                if stack[-1] == 0:
                    stack.pop()
                i += 1
            else:
                # 读取一个数字
                numStr = ""
                while i < n and preorder[i].isdigit():
                    numStr += preorder[i]
                    i += 1
                stack[-1] -= 1
                if stack[-1] == 0:
                    stack.pop()
                stack.append(2)
        return len(stack) == 0

4.执行结果