My solution using stack
Solution:\nAt 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 s
Solution:\nAt 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.\n\nHere is the steps of the algorithm: \n\n1)push a '*' when we encounter a number;\n\n2)push a '#' when we encounter a '#', \n\nthen judge whether the top two elements in the stack are '#',  -------------- question 1\n\nif yes for question 1, \n\njudge whether the third element is '*'  ---------------- question 2\n\nif yes for question 2, pop the top three element, then push a '#'.\n\nif no for question 2, then return false.\n\nif no for question 1, then continue.\n\nIn the end, if there is only one element in the stack and it is '#', then return true, else return false.\n\nThis algorithm runs in O(n) time complexity and O(n) space complexity.\n\nCode:\n\n\n    class Solution {  \n    public:  \n        bool isValidSerialization(string preorder) {  \n            stack<char>stk;  \n            int i,len=preorder.length();  \n            for(i=0;i<len;i++)  \n            {  \n                if(isdigit(preorder[i]))  \n                {  \n                    while(i<len&&isdigit(preorder[i]))  \n                    {  \n                        i++;  \n                    }  \n                    i--;  \n                    stk.push('*');  \n                }  \n                else if(preorder[i]=='#')  \n                {  \n                    stk.push('#');  \n                    while(stk.size()>=2&&stk.top()=='#')  \n                    {  \n                        stk.pop();  \n                        if(stk.top()=='#')//get the last two '#', change '*' to '#'  \n                        {  \n                            stk.pop();  \n                            if(stk.empty())return false;  \n                            if(stk.top()=='#')return false;  \n                            stk.pop();  \n                            stk.push('#');  \n                        }  \n                        else  \n                        {  \n                            stk.push('#');  \n                            break;  \n                        }  \n                    }  \n                }  \n            }  \n              \n            return stk.size()==1&&stk.top()=='#';  \n        }  \n    };
['C++']