Question
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 #.
Paste_Image.png
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
Code
public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null || preorder.length() == 0) return false;
String[] nodes = preorder.split(",");
if (nodes[0].equals("#")) {
if (nodes.length == 1) return true;
return false;
}
List<String> stack = new LinkedList<>();
for (int i = 0 ; i < nodes.length; i++) {
stack.add(nodes[i]);
while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#") && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
stack.remove(stack.size() - 1);
stack.remove(stack.size() - 1);
stack.remove(stack.size() - 1);
stack.add("#");
}
}
return stack.size() == 1 && stack.get(0).equals("#");
}
}
Solution
We can keep removing the leaf node until there is no one to remove. If a sequence is like "4 # #", change it to "#" and continue. We need a stack so that we can record previous removed nodes.
Here is an example:
Paste_Image.png
