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
#
._9_/ \3 2/ \ / \4 1 # 6/ \ / \ / \# # # # # #
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
Solution:
Idea is to simulate preorder traversal using a stack. Whenever meet a number, we push it to stack, which is to simulate go along the path down to the bottom left. When it is a #, we pop the stack. There are two situation during this process you should return a false. first, stack becomes empty but there are remaining string. Second, string is empty but stack is not.
Round 2 solution:
When meet a '#', we keep removing '#' and one additional node from the stack. After all available removal, we push back one '#'. So at the end, the valid solution will have only one '#' in the stack.
No comments:
Post a Comment