#
._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"
.Image we go through the input string, if we see number, we know we have to go down the tree until we encounter the "#", if we see "#", we will stop going down the tree and return. If we use a recursive function to process the input string, for a valid preorder string, we should successfully process all of the whole string. For invalid one we either prematurely terminate the process or go beyond the length of string.
There exists a very simplified version. Take a look at the lc discussion.
ReplyDeletethanks. i take a peek later.
Deletei am in the phase that i pretty much can solve all leetcode problems by myself now without looking at others' solutions. i am happy.
and my solution beat 85% java submissions... :)
Delete