0331. 验证二叉树的前序序列化

ITCharge大约 3 分钟

---

0331. 验证二叉树的前序序列化

标签：栈、树、字符串、二叉树
难度：中等

题目链接

0331. 验证二叉树的前序序列化 - 力扣

题目大意

描述：

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

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

给定一串以逗号分隔的序列。

要求：

验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

说明：

保证：每个以逗号分隔的字符或为一个整数或为一个表示 $null$ $n u ll$ 指针的 '#'。
你可以认为输入格式总是有效的
- 例如它永远不会包含两个连续的逗号，比如 "1,,3"。
注意：不允许重建树。
$1 \le preorder.length \le 10^{4}$ 。
$preorder$ 由以逗号 ',' 分隔的 $[0,10^{3}]$ 范围内的整数和 '#' 组成。

示例：

示例 1：

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

示例 2：

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

解题思路

思路 1：度数计算

核心思想：在二叉树的前序序列化中，每个非空节点都会提供 $2$ 个出度（左子树和右子树），每个空节点 # 会消耗 $1$ 个入度。如果序列化是有效的，那么最终度数应该为 $0$ 。

数学原理：

设 $degree$ 为当前可用的度数。
对于非空节点： $degree = degree + 2$ （提供 2 个出度）。
对于空节点 #： $degree = degree - 1$ （消耗 1 个入度）。
有效序列化的条件：遍历过程中 $degree \geq 0$ ，且最终 $degree = 0$ 。

算法步骤：

初始化：将输入字符串按逗号分割， $degree = 1$ （根节点提供 1 个初始度数）。
遍历序列：对于每个节点 $node$ ：
- 如果 node == "#"： $degree = degree - 1$ （空节点消耗 1 个度数）。
- 否则： $degree = degree + 2 - 1 = degree + 1$ （非空节点提供 2 个度数，消耗 1 个度数）。
- 如果 $degree < 0$ ，说明序列无效，返回 $false$ 。
验证结果：遍历结束后，如果 $degree = 0$ ，则序列有效，否则无效。

思路 1：代码

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # 将字符串按逗号分割成节点列表
        nodes = preorder.split(',')
        
        # 初始度数为 1（根节点提供 1 个初始度数）
        degree = 1
        
        # 遍历每个节点
        for node in nodes:
            # 先消耗 1 个度数（每个节点都需要消耗 1 个度数）
            degree -= 1
            
            # 如果度数变为负数，说明序列无效
            if degree < 0:
                return False
            
            # 如果不是空节点，则提供 2 个度数（左子树和右子树）
            if node != '#':
                degree += 2
        
        # 最终度数应该为 0
        return degree == 0

思路 1：复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是序列化字符串的长度。需要遍历一次字符串并分割节点。
空间复杂度： $O(n)$ ，用于存储分割后的节点列表。