本文主要是介绍【Leetcode】331. 验证二叉树的前序序列化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目
- 思路
- 代码
- 复杂度分析
- 时间复杂度
- 空间复杂度
- 结果
- 总结
题目
题目链接🔗
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
例如，上面的二叉树可以被序列化为字符串 " 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)
结果
总结
使用了递归的方法，通过模拟二叉树的前序遍历来判断序列是否有效。
这篇关于【Leetcode】331. 验证二叉树的前序序列化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
