题目 - 点击直达
- leetcode 331. 验证二叉树的前序序列化 | 中等难度
- 1. 题目详情
- 1. 原题链接
- 2. 基础框架
- 2. 解题思路
- 1. 题目分析
- 2. 算法原理
- 方法1:栈
- 方法2:计数
- 3. 时间复杂度
- 3. 代码实现
- 方法1:栈
- 方法2:计数
leetcode 331. 验证二叉树的前序序列化 | 中等难度
1. 题目详情
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
例如,上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”,其中 # 代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的
例如它永远不会包含两个连续的逗号,比如 “1,3” 。
注意:不允许重建树。
示例 1:
输入: preorder = “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true
示例 2:
输入: preorder = “1,#”
输出: false
示例 3:
输入: preorder = “9,#,#,1”
输出: false
提示:
1 < = p r e o r d e r . l e n g t h < = 104 1 <= preorder.length <= 104 1<=preorder.length<=104
preorder 由以逗号 “,” 分隔的 [0,100] 范围内的整数和 “#” 组成
1. 原题链接
leetcode 331. 验证二叉树的前序序列化
2. 基础框架
● Cpp代码框架
class Solution {
public:
bool isValidSerialization(string preorder) {
}
};
2. 解题思路
1. 题目分析
(
1
)
(1)
(1) 本题给出字符序列,判断该序列是否是二叉树的前序遍历。不允许创建二叉树。
(
2
)
(2)
(2)
(
3
)
(3)
(3)
2. 算法原理
方法1:栈
(
1
)
(1)
(1) 槽位:一个槽位可以被看作 当前二叉树中正在等待被节点填充的那些位置。二叉树的建立也伴随着槽位数量的变化。
(
2
)
(2)
(2) 每当遇到一个节点时:
- 如果遇到了空节点,则要消耗一个槽位;
- 如果遇到了非空节点,则除了消耗一个槽位外,还要再补充两个槽位。
方法2:计数
(
1
)
(1)
(1) 借助栈时的时间复杂度是
O
(
n
)
O(n)
O(n) , 空间复杂度是
O
(
n
)
O(n)
O(n) 。
(
2
)
(2)
(2) 可以不使用栈,而使用一个变量对槽位计数代替,空间复杂度降为
O
(
1
)
O(1)
O(1) 。
3. 时间复杂度
方法1:栈 时间复杂度 O ( n ) O(n) O(n), 空间复杂度 O ( n ) O(n) O(n)
遍历一遍字符序列,最差情况是字符序列的 数字字符 和 逗号 交替,最终字符序列的一半元素会全部入栈且不出栈。
方法2:计数 时间复杂度 O ( n ) O(n) O(n) ,空间复杂度 O ( 1 ) O(1) O(1)
使用变量计数代替栈
3. 代码实现
方法1:栈
class Solution {
public:
bool isValidSerialization(string preorder) {
int n = preorder.size();
stack<int> st;
int i = 0;
st.push(1);
while(i < n){
if(st.empty()) return false;
if(preorder[i] == ',') i++;
else if(preorder[i] == '#'){
st.top()--;
if(st.top() == 0) st.pop();
i++;
}
else{
while(i < n && preorder[i] != ',') i++;
st.top()--;
if(st.top() == 0) st.pop();
st.push(2);
}
}
return st.empty();
}
};
方法2:计数
class Solution {
public:
bool isValidSerialization(string preorder) {
int n = preorder.size();
int i = 0;
int slots = 1;
while(i < n){
if(slots == 0) return false;
if(preorder[i] == ',') i++;
else if(preorder[i] == '#'){
slots--;
i++;
}
else{
while(i < n && preorder[i] != ',') i++;
// slots--;
// slots += 2;
slots++;
}
}
return slots == 0;
}
};
T h e The The E n d End End