题解 | #序列化二叉树#

反序列化思路有点混乱，总之大致思路是层序遍历

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string tmp;
        if (!root) {
            tmp = "#,";
            char* res;
            res = (char*)malloc(tmp.length());
            memcpy(res, tmp.c_str(), tmp.length());
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto now = q.front();
            q.pop();
            if (now) {
                tmp += to_string(now->val) + ',';
                q.push(now->left);
                q.push(now->right);
            }
            else {
                tmp += "#,";
            }
        }
        char* res;
        res = (char*)malloc(tmp.length());
        memcpy(res, tmp.c_str(), tmp.length());
        return res;
        
    }
    TreeNode* Deserialize(char *str) {
        string tmp(str);
        stringstream ss(tmp);
        string item;
        queue<TreeNode*> q;
        TreeNode* now = nullptr, *root = nullptr;
        while (getline(ss, item, ',')) {
            if (item != "") {
                TreeNode* tn = nullptr;
                if (item != "#") {
                    tn = new TreeNode(stoi(item));
                }
                if (!root) {
                    if (!tn) return nullptr;
                    root = tn;
                    q.push(tn);
                }
                else if (!now) {
                    now = q.front();
                    q.pop();
                    now->left = tn;
                    if (tn) q.push(tn);
                }
                else {
                    now->right = tn;
                    now = nullptr;
                    if (tn) q.push(tn);
                }
            }
        }
        return root;
    }
};