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

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...