mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
90 lines
3.5 KiB
Markdown
90 lines
3.5 KiB
Markdown
# [331. Verify Preorder Serialization of a Binary Tree](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/)
|
||
|
||
# 思路
|
||
题目给定一个字符串，判断这个字符串能否表示成一个二叉树。
|
||
|
||
字符串中每个节点用逗号分割，所以我们可以先用`istringsteam`将这个字符串转换成输入流，然后用`getline`并设置分隔符delim为逗号（默认是换行符）不断获得每个节点node。
|
||
``` C++
|
||
istringstream in(preorder);
|
||
string node;
|
||
while(getline(in, node, ',')){
|
||
.....
|
||
}
|
||
```
|
||
|
||
## 思路一
|
||
|
||
这题的分类是栈，我们可以用栈解决，参考[讨论区](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78566/Java-intuitive-22ms-solution-with-stack)。
|
||
|
||
开辟一个栈，然后不断检查获得的节点node，有两种情况:
|
||
1. node为一个数，说明接下来会开辟一个以这个节点为根的子树，所以我们将其压栈；
|
||
2. node为#，此时根据栈顶划分又有两种情况：
|
||
```
|
||
2.1 栈顶为一个数，说明当前的#为左空节点，压栈就可以了（等待它的兄弟）。
|
||
2.2 栈顶为#，说明当前#为右空节点，栈顶为其左兄弟，应该出栈两次将其左兄弟及父亲删除，
|
||
然后回到第2.1开始不断循环，直到栈顶为一个数或者栈空，最后才将当前#入栈。
|
||
```
|
||
2.2中出栈两次是连贯的过程，所以如果第一次出栈后栈就空了则可以直接返回false。检查完毕后，如果栈中只剩下一个元素且就为#即可返回true，否则返回false。
|
||
|
||
以"9,3,4,#,#,1,#,#,2,#,6,#,#"为例的话上述过程如下图所示：
|
||
|
||
|
||
时空复杂度均为O(n)。
|
||
|
||
## 思路二
|
||
看[讨论区](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution)发现有一个不用栈的方法，常数时间复杂度。
|
||
|
||
在二叉树中，如果把空节点#当做是叶子，那么
|
||
* 所有非空节点有2个出度1个入度（除了根节点）；
|
||
* 所有空节点（即#）有0个出度1个入度。
|
||
|
||
我们维持一个变量diff代表 出度减去入度，初始为1（因为根节点入度为0而不是1）。遇到当前节点node时，先将diff减去1（因为不管node是否为空都有1个入度），
|
||
如果非空（即不是#），那还应该将diff加上2。这个过程中如果一旦遇到diff小于0则可返回false，最后返回 `diff==0`。
|
||
|
||
时间复杂度O(n), 空间复杂度O(1)。
|
||
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
bool isValidSerialization(string preorder) {
|
||
istringstream in(preorder);
|
||
string node;
|
||
|
||
stack<char>stk;
|
||
while(getline(in, node, ',')){
|
||
if(node != "#") stk.push('n');
|
||
else{
|
||
while(!stk.empty() && stk.top() == '#'){
|
||
stk.pop();
|
||
if (stk.empty()) return false;
|
||
stk.pop();
|
||
}
|
||
stk.push('#');
|
||
}
|
||
}
|
||
return stk.size() == 1 && stk.top() == '#';
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
bool isValidSerialization(string preorder) {
|
||
istringstream in(preorder);
|
||
string node;
|
||
|
||
int diff = 1;
|
||
while(getline(in, node, ',')){
|
||
if (--diff < 0) return false;
|
||
if (node != "#") diff += 2;
|
||
}
|
||
return diff == 0;
|
||
}
|
||
};
|
||
```
|