# Leetcode 331 - Verify preorder serialization of a binary tree

`Note:`

`DFS`

- Why would it work? If we can finish iterating the
`preorder`

array, it means it’s a good binary tree. - What if there are some extra
`nodes`

at the end? Then`res !== preorder.length`

. - What if there are some
`nodes`

missing? Because we check`i >= preorder.length`

, we can still get`false`

.

- Why would it work? If we can finish iterating the
`Indegree & Outdegree`

.- For a binary tree,
`indegree === outdegree`

`Root`

node provides`2 outdegree`

.`#`

node provides`1 indegree`

.- Normal node provides
`1 indegree`

and`2 outdegree`

.

- For a binary tree,

`Question:`

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,#,#" |

`Code:`

1 | /** |

1 | /** |