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

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Solution:

Level traverse, the number of non-null node determines the number of next level nodes.

Using the example in the question,

Level 1 has 1 non-null node, so level 2 should have 2 nodes,

Level 2 has 2 non-null nodes, so level 3 should have 4 nodes,

Level 3 has 3 non-null nodes, so level 4 should have 6 nodes,

level 5 has 0 non-null nodes, so level 6 should be empty.

So we can use a count variable to keep track how many nodes we will have to next level,

So for the first level we should have count =1,

because there is 1 non-null node, count+=2, means there will be 3 in total of node to level 2,

We keep the iteration until we either hit the last node or we hit the total counts.

So if the total count to the last level is the same as the total number of nodes, which means the string is a valid preorder serialization. False otherwise.

Time complexity: O(n)

 public boolean isValidSerialization(String preorder) {  
     if(preorder==null || preorder.length()==0) return false;  
     String[] nodes=preorder.split(",");  
     int count=1;  
     for(int i=0;i<nodes.length && i<count;i++){  
       if(!nodes[i].equals("#")) count+=2;  
     }  
     return count==nodes.length;  
   }