# 331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as `#`.

``````     _9_
/   \
3     2
/ \   / \
4   1  #  6
/ \ / \   / \
# # # #   # #
``````

For example, the above binary tree can be serialized to the string `"9,3,4,#,#,1,#,#,2,#,6,#,#"`, where `#` represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character `'#'` representing `null` pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as `"1,,3"`.

Example 1:

``````Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
``````

Example 2:

``````Input: "1,#"
Output: false
``````

Example 3:

``````Input: "9,#,#,1"
Output: false
``````

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

1. 数字的个数总是比#号少一个

2. 最后一个一定是#号

``````class Solution {
public:
bool isValidSerialization(string preorder) {
istringstream in(preorder);
vector<string> v;
string t = "";
int cnt = 0;
while (getline(in, t, ',')) v.push_back(t);
for (int i = 0; i < v.size() - 1; ++i) {
if (v[i] == "#") {
if (cnt == 0) return false;
--cnt;
} else ++cnt;
}
return cnt == 0 && v.back() == "#";
}
};
``````

``````class Solution {
public:
bool isValidSerialization(string preorder) {
istringstream in(preorder);
string t = "";
int degree = 1;
bool degree_is_zero = false;;
while (getline(in, t, ',')) {
if (degree_is_zero) return false;
if (t == "#") {
if (--degree == 0) degree_is_zero = true;
} else ++degree;
}
return degree == 0;
}
};
``````

``````class Solution {
public:
bool isValidSerialization(string preorder) {
int capacity = 1;
preorder += ",";
for (int i = 0; i < preorder.size(); ++i) {
if (preorder[i] != ',') continue;
if (--capacity < 0) return false;
if (preorder[i - 1] != '#') capacity += 2;
}
return capacity == 0;
}
};
``````

Serialize and Deserialize Binary Tree

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

https://discuss.leetcode.com/topic/36035/2-lines-java-using-regex

https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution

https://discuss.leetcode.com/topic/45326/c-4ms-solution-o-1-space-o-n-time

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation