331

331. Verify Preorder Serialization of a Binary Tree (Medium)

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.

 

Example 1:

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

Example 2:

Input: preorder = "1,#"
Output: false

Example 3:

Input: preorder = "9,#,#,1"
Output: false

 

Constraints:

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

Companies: TikTok, Google

Related Topics:
String, Stack, Tree, Binary Tree

Solution 1.

// OJ: https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stack<int> s;
        stringstream ss(preorder);
        string node;
        bool ended = false;
        while (getline(ss, node, ',')) {
            if (ended) return false;
            if (node == "#") {
                while (s.size() && ++s.top() == 2) s.pop();
                if (s.empty()) ended = true;
            } else {
                s.push(0);
            }
        }
        return s.empty();
    }
};