Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use preorder traversal. When you encounter a non-null node, you record the node's value. If it is a null node, you record using a sentinel value such as '#'.
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 is either an integer or the character '#' representing a null pointer.
You may assume that the input format is always valid:
- It will 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
trueThe string is a valid preorder serialization of a binary tree.
Example 2
Input
preorder = "1,#"Output
falseThe serialization ends before completing a valid binary tree structure.
Constraints
- 1 <= preorder.length <= 10^4
- preorder consist of integers in the range [0, 100] and '#' separated by commas ','.