331 Verify Preorder Serialization of a Binary Tree

Problem:

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

Solutions:

``````public class Solution {
private int index = 0;
public boolean isValidSerialization(String preorder) {
String[] vals = preorder.split(",");
if (vals.length % 2 == 0) {
return false;
}
index = 0;
return visit(vals) && index == vals.length;
}
private boolean visit(String[] vals) {
if (index >= vals.length) {
return false;
}
if (vals[index].equals("#")) {
index ++;
return true;
}
index ++;
return visit(vals) && visit(vals);
}
}
``````
``````public class Solution {
private int index = 0;
public boolean isValidSerialization(String preorder) {
String[] vals = preorder.split(",");
if (vals.length % 2 == 0) {
return false;
}
Stack<String> s = new Stack<String>();
for (int i = 0; i < vals.length; i ++) {
s.push(vals[i]);
while (s.size() >= 3) {
String s1 = s.pop();
String s2 = s.pop();
String s3 = s.pop();
if (s1.equals("#") && s2.equals("#") && !s3.equals("#")) {
s.push("#");
}
else {
s.push(s3);
s.push(s2);
s.push(s1);
break;
}
}
}
if (s.size() == 1 && s.pop().equals("#")) {
return true;
}
else {
return false;
}
}
}
``````
``````public class Solution {
private int index = 0;
public boolean isValidSerialization(String preorder) {
String[] vals = preorder.split(",");
if (vals.length % 2 == 0) {
return false;
}
int diff = 1; // outdegree - indegree
for (String s:vals) {
diff --;
if (diff < 0) {
return false;
}
if (!s.equals("#")) {
diff += 2;
}
}
return diff == 0;
}
}
``````