LeetCode Q331: Verify Preorder Serialization of a Binary Tree

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:

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

Return true

Example 2:

"1,#"

Return false

Example 3:

"9,#,#,1"

Return false

Solution:

Idea is to simulate preorder traversal using a stack. Whenever meet a number, we push it to stack, which is to simulate go along the path down to the bottom left. When it is a #, we pop the stack. There are two situation during this process you should return a false. first, stack becomes empty but there are remaining string. Second, string is empty but stack is not.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	if(preorder.length()==0)
	return false;
	vector<string> str;
	int i=0;
	string s;
	while(i<=preorder.length()){
	if(preorder[i]==','||i==preorder.length()){
	str.push_back(s);
	s=string("");
	}else{
	s=s+string(1, preorder[i]);
	}
	i++;
	}
	stack<string> myStack;
	i=0;
	while(i<str.size()){
	if(str[i]!="#"){
	myStack.push(str[i]);
	}else{
	if(myStack.empty()&&i!=str.size()-1)
	return false;
	if(!myStack.empty()&&i==str.size()-1)
	return false;
	if(i!=str.size()-1)
	myStack.pop();
	}
	i++;
	}
	return myStack.empty();
	}
	};

view raw Q331.cpp hosted with ❤ by GitHub

Round 2 solution:
When meet a '#', we keep removing '#' and one additional node from the stack. After all available removal, we push back one '#'. So at the end, the valid solution will have only one '#' in the stack.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	bool res=true;
	stack<string> myStack;
	if(preorder.empty())
	return res;
	int p=0;
	string str;
	while(p<preorder.length()&&preorder[p]!=','){
	str+=string(1, preorder[p]);
	p++;
	}
	p++;
	myStack.push(str);
	str=string("");
	string pre = preorder;
	while(!myStack.empty()&&p<=preorder.length()){
	if(p==preorder.length()||pre[p]==','){
	if(str==string(1, '#')){
	while(!myStack.empty() && myStack.top()==string("#")){
	myStack.pop();
	if(myStack.empty())
	return false;
	myStack.pop();
	}
	myStack.push(string("#"));
	}else{
	myStack.push(str);
	}
	str=string("");
	}else{
	str=str+string(1, pre[p]);
	}
	p++;
	}
	if(myStack.size()==1&&myStack.top()==string("#"))
	return true;
	else
	return false;
	}
	};

view raw Q331Rnd2.cpp hosted with ❤ by GitHub