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
Understand the problem:"9,#,#,1"
Return
false
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