331. Verify Preorder Serialization of a Binary Tree
Description
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:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true
Example 2:
Input: preorder = "1,#" Output: false
Example 3:
Input: preorder = "9,#,#,1" Output: false
Constraints:
1 <= preorder.length <= 104
preorder
consist of integers in the range[0, 100]
and'#'
separated by commas','
.
Solutions
Solution 1: Stack
We split the string preorder
into an array by commas, then traverse the array. If we encounter two consecutive '#'
and the third element is not '#'
, we replace these three elements with a single '#'
. This process continues until the array traversal is complete.
Finally, we check whether the length of the array is $1$ and whether the only element in the array is '#'
.
The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the string preorder
.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 |
|