# My solution using stack

• Solution:
At the first glance, I have no idea about the problem. So I decided to simulate some cases to find whether there are some regulations. After trying several cases I found that the value before two consecutive '#'s should be a leaf and there are two consecutive '#'s after a leaf. So I think out a solution using stack.

Here is the steps of the algorithm:

1)push a '*' when we encounter a number;

2)push a '#' when we encounter a '#',

then judge whether the top two elements in the stack are '#', -------------- question 1

if yes for question 1,

judge whether the third element is '*' ---------------- question 2

if yes for question 2, pop the top three element, then push a '#'.

if no for question 2, then return false.

if no for question 1, then continue.

In the end, if there is only one element in the stack and it is '#', then return true, else return false.

This algorithm runs in O(n) time complexity and O(n) space complexity.

Code:

``````class Solution {
public:
bool isValidSerialization(string preorder) {
stack<char>stk;
int i,len=preorder.length();
for(i=0;i<len;i++)
{
if(isdigit(preorder[i]))
{
while(i<len&&isdigit(preorder[i]))
{
i++;
}
i--;
stk.push('*');
}
else if(preorder[i]=='#')
{
stk.push('#');
while(stk.size()>=2&&stk.top()=='#')
{
stk.pop();
if(stk.top()=='#')//get the last two '#', change '*' to '#'
{
stk.pop();
if(stk.empty())return false;
if(stk.top()=='#')return false;
stk.pop();
stk.push('#');
}
else
{
stk.push('#');
break;
}
}
}
}

return stk.size()==1&&stk.top()=='#';
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.