文章目录
- 题目
- 思路
- 代码
- 复杂度分析
- 时间复杂度
- 空间复杂度
- 结果
- 总结
题目
题目链接🔗
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
例如,上面的二叉树可以被序列化为字符串
"
9
,
3
,
4
,
#
,
#
,
1
,
#
,
#
,
2
,
#
,
6
,
#
,
#
"
"9,3,4,\#,\#,1,\#,\#,2,\#,6,\#,\#"
"9,3,4,#,#,1,#,#,2,#,6,#,#",其中
#
\#
# 代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
保证 每个以逗号分隔的字符或为一个整数或为一个表示 n u l l null null 指针的 ′ # ′ '\#' ′#′ 。
你可以认为输入格式总是有效的
例如它永远不会包含两个连续的逗号,比如
"
1
,
,
3
"
"1,,3"
"1,,3" 。
注意:不允许重建树。
示例 1:
输入: p r e o r d e r = " 9 , 3 , 4 , # , # , 1 , # , # , 2 , # , 6 , # , # " preorder = "9,3,4,\#,\#,1,\#,\#,2,\#,6,\#,\#" preorder="9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: t r u e true true
示例 2:
输入: p r e o r d e r = " 1 , # " preorder = "1,\#" preorder="1,#"
输出: f a l s e false false
示例 3:
输入: p r e o r d e r = " 9 , # , # , 1 " preorder = "9,\#,\#,1" preorder="9,#,#,1"
输出: f a l s e false false
提示:
- 1 ≤ p r e o r d e r . l e n g t h ≤ 1 0 4 1 \leq preorder.length \leq 10^4 1≤preorder.length≤104
- p r e o r d e r preorder preorder 由以逗号 " , " "," "," 分隔的 [ 0 , 100 ] [0,100] [0,100] 范围内的整数和 “ # ” “\#” “#” 组成
思路
这道题要求验证给定的序列是否是正确的二叉树的前序序列化,而且不能重建树。可以使用迭代的方法来模拟整个过程。
可以观察到一个有效的二叉树序列化中,非空节点后面必然跟着两个 ′ # ′ '\#' ′#′表示空节点,因为二叉树中的每个节点都有两个子节点(包括空节点)。所以可以遍历序列,当遇到一个非空节点时,记录之后的两个节点是否为 ′ # ′ '\#' ′#′,如果是则继续遍历,否则返回 f a l s e false false。遍历完成后,如果指针指向了序列的末尾,则返回 t r u e true true,否则返回 f a l s e false false。
代码
class Solution {
public:
bool isValidSerialization(string preorder) {
int p = 0;
return dfs(preorder, p) && p == preorder.size();
}
bool dfs(const string& preorder, int& p) {
if (p == preorder.size()) {
return false;
}
if (preorder[p] == '#') {
if (p == preorder.size() - 1) p++;
else p += 2;
return true;
}
while (p < preorder.size() && preorder[p] != ',') p++;
if (p == preorder.size()) return false;
p += 1;
return dfs(preorder, p) && dfs(preorder, p);
}
};
复杂度分析
时间复杂度
遍历整个序列,时间复杂度为 O ( n ) O(n) O(n)
空间复杂度
递归调用的深度最坏情况下为 O ( n ) O(n) O(n)
结果
总结
使用了递归的方法,通过模拟二叉树的前序遍历来判断序列是否有效。