331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use preorder 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 ‘#’.

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 preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that 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”.

Note: You are not allowed to reconstruct the tree.

class Solution {
    fun isValidSerialization(preorder: String): Boolean {
        val tokens = preorder.split(',');
        if(tokens[0] == "#") return tokens.size == 1;
        val cntSt = mutableListOf(0);
        for(i in 1 until tokens.size) {
            if(cntSt.isEmpty()) return false;
            cntSt[cntSt.size - 1] += 1;
            if(cntSt[cntSt.size - 1] > 2) return false;
            if(tokens[i]=="#") {
                while(!cntSt.isEmpty() && cntSt[cntSt.size-1] == 2)
                    cntSt.removeAt(cntSt.size-1);
            } else {
                cntSt.add(0);
            }
        }
        return cntSt.isEmpty();
    }
}