LeetCode: 331. Verify Preorder Serialization of a Binary Tree

The Problem

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 '#'.

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.

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Constraints:

• 1 <= preorder.length <= 104
• preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solution

We chose an iterative approach to solve the problem. When we evaluated our solution on the LeetCode platform, here are the results:

Here's the code that led us to this result.

bool isValidSerialization(string preorder) {
    stringstream str(preorder);
    string node;
    int count = 1;

    while(getline(str, node, ',')){
        --count;
        if(count < 0) return false;
        if(node != "#") count = count + 2;
    }
    return count == 0;
}

Here's a simplified explanation:

1. It starts by splitting the preorder string into individual nodes using a comma (',') as the delimiter.
2. It initializes a variable count to 1. This variable represents the number of available slots for nodes in the tree.

It iterates through the nodes one by one:

• For each node encountered, it decrements count by 1.
• If count becomes negative at any point, it means there are more nodes in the traversal than slots available, which is not valid. In this case, it returns false.
• If the node is not a '#' (representing a valid node), it means there are two more slots available for child nodes, so it increments count by 2.

1. After processing all nodes, it checks if count is back to 0. If it is, it means the traversal is valid, and it returns true; otherwise, it returns false.