## 题目地址(331. 验证二叉树的前序序列化)

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

## 题目描述

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

     _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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
