首页 > 其他 > 详细

LeetCode "Verify Preorder Serialization of a Binary Tree"

时间:2016-02-03 06:39:58      阅读:114      评论:0      收藏:0      [点我收藏+]

Yes a typical stack based problem. Please take care of corner cases.

class Solution {
public:
    bool isValidSerialization(string preorder) 
    {        
        //    Get tokens.
        vector<string> tokens; // true - is num; false - is null
        int i = 0; string tk;
        while(i < preorder.length())
        {
            char c = preorder[i];
            if(c == ,)
            {
                tokens.push_back(tk);
                tk.clear();
            }
            else
            {
                tk += c;
            }
            i ++;
        }
        tokens.push_back(tk);
        
        int n = tokens.size();
        if(n==1) return tokens[0] == "#";
        if (n < 3) return false;
        
        //    Go
        typedef pair<string, bool> Rec; // value - is on right
        i = 0;
        stack<Rec> stk;
        if(tokens[0] != "#")
            stk.push(Rec(tokens[i++], false));
        while(!stk.empty() && (i < n))
        {
            string tk = tokens[i++];
            if(tk == "#") // ‘#‘
            {
                if(!stk.top().second) // switch to right
                {
                    stk.top().second = true;
                }
                else
                {
                    while(!stk.empty() && stk.top().second) stk.pop();
                    if(!stk.empty()) stk.top().second = true;
                }
            }
            else 
            {
                stk.push(Rec(tk, false));
            }
        }

        return stk.empty() && (i == n);
    }
};

LeetCode "Verify Preorder Serialization of a Binary Tree"

原文:http://www.cnblogs.com/tonix/p/5178896.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!