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:

Return

`"9,3,4,#,#,1,#,#,2,#,6,#,#"`

Return

`true`

Example 2:

Return

`"1,#"`

Return

`false`

Example 3:

Return

`"9,#,#,1"`

Return

`false`

**Understand the problem:**

The key of the problem is if a preorder traversal of a binary tree is valid, a leaf node must have the sequence like "number, #, #". Therefore, we can start from leaf nodes of tree, remove the leaf nodes by replacing the number, #, # by a single # until the tree becomes empty.

**Code (Java):**

public class Solution { public boolean isValidSerialization(String preorder) { if (preorder == null || preorder.length() == 0) { return true; } String[] nodes = preorder.split(","); Stack<String> stack = new Stack<>(); for (String node : nodes) { if (node.equals("#")) { while (!stack.isEmpty() && stack.peek().equals("#")) { stack.pop(); if (stack.isEmpty()) { return false; } stack.pop(); } } stack.push(node); } return stack.size() == 1 && stack.peek().equals("#"); } }

## No comments:

## Post a Comment