One way to serialize a binary tree is to use pre-oder 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
Solution. I came up with the first solution naturally by using recursion. The idea is that if current is ‘#’, we simply return true. If current is a number, call validHelper 2 times with pos++. In the end, return true if pos == list.length – 1.
public static boolean isValidSerialization(String preorder) {
String[] list = preorder.split(",");
int[] pos = new int[] {-1};
if (!validHelper(list, pos) || pos[0] != list.length - 1) { // in the end, pos[0] should equal len - 1
return false;
}
return true;
}
public static boolean validHelper(String[] list, int[] pos) {
pos[0]++;
if (pos[0] >= list.length) { // add pos[0] first
return false;
}
if (list[pos[0]].equals("#")) { // if is '#', return true.
return true;
}
// if is a number, call 2 times.
return validHelper(list, pos) && validHelper(list, pos);
}
There is another cool solution from this post. It’s about number of internal node and leaf node. Basically, number of leaf node should be always greater than number of internal node + 1. We use diff to measure the difference between number of internal node and leaf node. For each loop, diff–. If current node is an internal node, diff = diff + 2.
public static boolean isValidSerialization2(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1;
for (String node : nodes) {
if (--diff < 0) {
return false;
}
if (!node.equals("#")) {
diff += 2;
}
}
return diff == 0;
}
Check my code on github: link