Problem: 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 # or $. Check our previous problem here.
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.
Example:
Input:"1,2,3,#,#,4,#,#,5,#,6,#,#"Output:true
Approach: We can keep trimming the leaves until there is no one to remove. If a sequence is like "3 # #", change it to "#" and continue. We can use stack to implement it easily. See by above example:
#
(if in stack only # is remaining, return true else false)
Implementation in C#:
public static bool IsValidSerialization(string preorder)
{
if (string.IsNullOrWhiteSpace(preorder))
{
return false;
}
string[] nodesValueArr = preorder.Split(',');
Stack<string> stack = new Stack<string>();
foreach(string nodeValue in nodesValueArr)
{
if (stack.Count == 0 || !nodeValue.Equals("#"))
{
stack.Push(nodeValue);
}
else
{
while(stack.Count > 0 && stack.Peek().Equals("#"))
{
stack.Pop();
if (stack.Count == 0)
{
return false;
}
else
{
stack.Pop();
}
}
stack.Push(nodeValue);
}
}
return stack.Count == 1 && stack.Peek().Equals("#");
}
Complexity: O(n)
No comments:
Post a Comment