Verify Preorder Serialization Of A Binary Tree Problem


Description

LeetCode Problem 331.

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= preorder.length <= 10^4
  • preorder consist of integers in the range [0, 100] and ‘#’ separated by commas ‘,’.


Sample C++ Code

We use nodes to count the nodes we are allowed to have next. Every time we get a new node we decrease nodes, if we got below zero it’s false. If we get a non-null node, we can have after it two more nodes. At the end, we are supposed to end up with nodes == 0, otherwise the tree is not good.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stringstream ss(preorder);
        string curr;
        int nodes = 1;
        while (getline(ss, curr, ',')) {
            nodes--;
            if (nodes < 0) return false;
            if (curr != "#") nodes += 2;
        }
        return nodes == 0;
    }
};




Related Posts

Daily Temperatures Problem

LeetCode 739. Given an array of integers temperatures represents the...

Baseball Game Problem

LeetCode 682. You are keeping score for a baseball game...

Asteroid Collision Problem

LeetCode 735. We are given an array asteroids of integers...

Tag Validator Problem

LeetCode 591. Given a string representing a code snippet, implement...

Next Greater Element II Problem

LeetCode 503. Given a circular integer array nums (i.e., the...

Verify Preorder Serialization Of A Binary Tree Problem

LeetCode 331. One way to serialize a binary tree is...