# 0331. 验证二叉树的前序序列化
### 题目地址(331. 验证二叉树的前序序列化)
### 题目描述
```
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false
```
### 前置知识
* 图论
### 公司
* 暂无
### 思路
首先明确两点：
1. 树是一种特殊的图，因此图的特性在树中也满足。
2. 图中的点的入度总和 = 图中的点的出度总和。
稍微解释一下第二点：对于一个图来说，它是由点和边构成的。如果初始化图有 n 个点 ，接下来在 n 个点之间连接 m 条边。那么**每连接一条边实际上整个图的入度和出度都增加一**，因此任意中的入度和出度之和是相等的。
由于我们可以遍历前序遍历序列并计算入度和出度，一旦最后入度和出度不等，那么意味着肯定是不合法的。
如果入度和出度和相等，就一定是合法的么？也不一定。比如题目给出的示例三："9,#,#,1"。因此我们需要额外判断在**整个遍历过程出度是否小于入度**，如果小于了，那么意味着不合法。（想想为什么？）
那么还需要别的判断么？换句话说，这就够了么？由于我们只需要判断入度和出度的**相对关系**，因此没有必要使用两个变量，而是一个变量表示二者的差值即可。
算法：
* 初始化入度和出度的差值 diff 为 0
* 遍历 preorder，遇到任何节点都要增加一个入度。 除此外，遇到非空节点增加两个出度。
* 如果遍历过程 diff 非法可提前退出，返回 false
* 最后判断 diff 是否等于 0
### 关键点
* 从入度和出度的角度思考
### 代码
* 语言支持：Python3
Python3 Code:
注意我最后判断的是 diff == -1 而不是 diff == 0，原因在于我代码利用了一个虚拟节点 dummy，dummy 直接指向了 root，其中 dummy 只有一个子节点，而不是两个(但是代码算成两个了)。这点需要大家注意，并不是和思路对不上。
```python
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
diff = 0
for node in preorder.split(","):
diff -= 1
if diff < -1:
return False
if node != "#":
diff += 2
return diff == -1
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$
### 扩展
除此之外还有人给出了[栈的解法](https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/)，大家也可以参考下，作为思路扩展也是不错的。
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/331.verify-preorder-serialization-of-a-binary-tree.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.