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:
Example 2:
Example 3:
Constraints:
1 <= preorder.length <= 10^4
preorder
consist of integers in the range[0, 100]
and'#'
separated by commas','
.
解ι‘
δ½Ώη¨ indegree, outdegree δΎεε€ζ·οΌεθθ¨θ«ειεθΆ η₯η解η
Runtime: 0 ms, faster than 100%
Memory Usage: 2.2 MB, less than 93.55%
Last updated