Leetcode 331 Solution

This article provides solution to leetcode question 331 (verify-preorder-serialization-of-a-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 331" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree

Solution

class Solution {
public:
    bool isValidSerialization(string preorder) {
        preorder += ',';
        string curr;



        int status = 0;
        for (int i = 0; i < preorder.size(); i++)
        {
            if (preorder[i] == '#')
                status = 1;
            else if (preorder[i] == ',')
            {
                if (status == 1)
                    curr += '#';
                else if (status == 2)
                    curr += '0';
            }
            else
                status = 2;
        }



        while (true)
        {
            string next;



            for (int i = 0; i < (int)curr.size(); i++)
            {
                if (i + 2 < curr.size() && curr[i] != '#' && curr[i + 1] == '#' && curr[i + 2] == '#')
                {
                    next += '#';
                    i += 2;
                }
                else
                    next += curr[i];
            }



            if (curr.size() == next.size())
                break;



            curr = next;
        }



        return curr.size() == 1 && curr[0] == '#';
    }
};