序列化二叉树

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

深搜
https://leetcode.com/discuss/76182/clean-c-solution

/**
 * 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 == nullptr) return "#";
        return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return mydeserialize(data);
    }
    TreeNode* mydeserialize(string& data) {
        if (data[0]=='#') {
            if(data.size() > 1) data = data.substr(2);
            return nullptr;
        } else {
            TreeNode* node = new TreeNode(helper(data));
            node->left = mydeserialize(data);
            node->right = mydeserialize(data);
            return node;
        }
    }
private:
    int helper(string& data) {
        int pos = data.find(',');
        int val = stoi(data.substr(0,pos));
        data = data.substr(pos+1);
        return val;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));    

广搜

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
 //"[1,2,3,null,null,4,5]"
 //1,2,
class Codec {
public:
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ret;
        if(root == NULL) {
            return "null";
        }
        queue<TreeNode *> q;
        q.push(root);
        ret += to_string(root->val);
        while(!q.empty()) {
            TreeNode * n = q.front(); q.pop();
            if(n->left) {
                ret += "," + to_string(n->left->val);
                q.push(n->left);
            } else {
                ret+=",null";
            }
            if(n->right) {
                ret+=","+to_string(n->right->val);
                q.push(n->right);
            } else {
                ret += ",null";
            }
        }
        return ret;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode * root;
        if(data[0]=='n'){
            return NULL;
        } else {
            root = new TreeNode(helper(data));
        }
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode * n = q.front();q.pop();
            if(data[0] != 'n') {
                n->left = new TreeNode(helper(data));
                q.push(n->left);
            } else {
                if(data.size() > 5)
                    data = data.substr(5);
            }
            if(data[0] != 'n'){
                n->right = new TreeNode(helper(data));
                q.push(n->right);
            } else {
                if(data.size() > 5)
                    data = data.substr(5);
            }
        }
        return root;
    }
    
    int helper(string& data) {
        int pos = data.find(',');
        int val = stoi(data.substr(0,pos));
        data = data.substr(pos+1);
        return val;
    }
};


// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));