# LeetCode Verify Preorder Serialization of a Binary Tree

LeetCode 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:
`"9,3,4,#,#,1,#,#,2,#,6,#,#"`
Return `true`
Example 2:
`"1,#"`
Return `false`
Example 3:
`"9,#,#,1"`
Return `false`

• 9,3,4,#,# → 9,3,#
• 9,3,#,1,#,# → 9,3,#,# → 9,#
• 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #

```class Solution {
public:
bool isValidSerialization(string preorder) {
stack<string> stk;
int i = 0, j = 0, n = preorder.size();
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (node == "#") {
while (!stk.empty() && stk.top() == "#") {
stk.pop();
if (stk.empty())return false;
stk.pop();
}
}
stk.push(node);
i = ++j;
}
return stk.size() == 1 && stk.top() == "#";
}
};
```

```class Solution {
public:
bool isValidSerialization(string preorder) {
int i = 0, j = 0, n = preorder.size(), diff = 1;
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (--diff < 0)return false;
if (node != "#")diff += 2;
i = ++j;
}
return diff == 0;
}
};
```

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

```class Solution3 {
public:
bool isValidSerialization(string preorder) {
int leaves = 0, nonleaves = 0;
int i = 0, j = 0, n = preorder.size();
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (node == "#")++leaves;
else ++nonleaves;
i = ++j;
if (leaves - nonleaves == 1 && j < n)return false;
}
return leaves - nonleaves == 1;
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.