297. Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

瞎写，懒得看别人写法了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "[]";
        queue<TreeNode*> q;
        string res = "[";
        q.push(root);
        int nodeNum = 1;
        while(!q.empty() && nodeNum)
        {
            auto p = q.front();
            q.pop();
            if(p)
            {
                nodeNum += (p->left ? 1 : 0) + (p->right ? 1 : 0);
                q.push(p->left);
                q.push(p->right);
                --nodeNum;
                res += to_string(p->val);
            }else
                res += "null";
            res += ",";
        }
        res.back() = ']';
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<TreeNode *> q;
        auto nodes = parseString(data);
        TreeNode *root = nullptr;
        bool leftNotIn = true;
        for (const auto &node : nodes)
        {
            if (q.empty())
                q.push(root = new TreeNode(*node));
            else
            {
                auto curNode = q.front();
                if (!curNode->left && leftNotIn)
                {
                    if (node)
                        q.push(curNode->left = new TreeNode(*node));
                    else
                        curNode->left = nullptr;
                    leftNotIn = false;
                }
                else if (!curNode->right)
                {
                    if (node)
                        q.push(curNode->right = new TreeNode(*node));
                    else
                        curNode->right = nullptr;
                    q.pop();
                    leftNotIn = true;
                }
            }
        }
        return root;
    }
private:
    bool isDigitalOrCharacter(const char &ch)
    {
        return ('0' <= ch && '9' >= ch) || ('a' <= ch && 'z' >= ch) || ch == '-';
    }

    bool isSplitCondition(const char &ch)
    {
        return ch == ',' || ch == ']';
    }
    std::vector<std::shared_ptr<int>> parseString(std::string &s)
    {
        std::queue<char> cache;
        std::vector<std::shared_ptr<int>> res;
        auto begin = s.begin();
        auto end = s.end() - 1;
        while (*begin != '[')
            ++begin;
        while (*end != ']')
            --end;
        ++begin;
        for (; begin != end + 1; ++begin)
        {
            if (isSplitCondition(*begin))
            {
                int realNum = 0;
                int positive = 1;
                if (cache.empty())
                    return {};
                if (cache.front() == '-')
                {
                    positive = -1;
                    cache.pop();
                }
                while (!cache.empty())
                {
                    realNum = realNum * 10 + static_cast<int>(cache.front() - '0');
                    cache.pop();
                }
                if (realNum == 69560) // null
                    res.push_back(nullptr);
                else
                    res.push_back(std::make_shared<int>(realNum * positive));
            }
            else if (isDigitalOrCharacter(*begin))
            {
                cache.push(*begin);
            }
        }
        return res;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

1620118342754.png

r

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "";
        queue<TreeNode*> q;
        q.push(root);
        string ret;
        while(!q.empty()) {
            for(auto i = q.size(); i > 0; --i) {
                auto p = q.front();
                q.pop();
                if(!p)
                    ret += "n ";
                else {
                    ret += to_string(p->val) + " ";
                    q.push(p->left);
                    q.push(p->right);
                }
            }
        }
        ret.pop_back();
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        stringstream ss(data);
        string cur;
        getline(ss, cur, ' ');
        auto root = new TreeNode(stoi(cur));
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            for(auto i = q.size(); i > 0; --i) {
                auto p = q.front();
                q.pop();
                getline(ss, cur, ' ');
                if(cur[0] != 'n') {
                    p->left = new TreeNode(stoi(cur));
                    q.push(p->left);
                }
                getline(ss, cur, ' ');
                if(cur[0] != 'n') {
                    p->right = new TreeNode(stoi(cur));
                    q.push(p->right);
                }
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));