Verify Preorder Serialization of a Binary Tree 4

Title: Verify Preorder Serialization of a Binary Tree Source: leetcode.com

One way to serialize a binary tree is to use pre-order 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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

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".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Java solution

Python solution

Rate this post

4 thoughts on “Verify Preorder Serialization of a Binary Tree

  1. Reply priyatamil Mar 30,2016 4:44 pm

    Now it is known to me that articles is nothing but inspiring is everything to do something great.Thanks for sharing that wonderful useful information,given programming coding was very excellent and easily observe all provided information.

  2. Reply Java classes Aug 2,2017 2:13 pm

    You have shared useful programming with us. Thanks for your effort.

  3. Pingback: N-ary Tree PreOrder Traversal - Coddicted

Leave a Reply