297. Serialize and Deserialize Binary Tree

O(n) BFS
“1 2 3 # # 4 5 # # # # “

/**
 * 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) {
        string res;
        queue<TreeNode *> q{{root}};
        while (!q.empty()) {
            auto n = q.front(); q.pop();
            if (n) {
                res += to_string(n->val);
                q.push(n->left);
                q.push(n->right);
            } else {
                res += "#";
            }
            res += " ";
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        TreeNode dummy_root(0);
        queue<pair<bool, TreeNode *>> q{{{true, &dummy_root}}};
        string s;
        while (input >> s) {
            TreeNode *n = (s == "#" ? nullptr : new TreeNode(stoi(s)));
            if (q.front().first) {
                q.front().second->right = n;
                q.pop();
            } else {
                q.front().second->left = n;
                q.front().first = true;
            }
            if (n) { // 这里要检查是否是空指针，因为要对queue里的指针设左右子树，不能出现空指针
                q.emplace(false, n);
            }
        }
        return dummy_root.right;
    }
};

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

preorder dfs
“1 2 # # 3 4 # # 5 # # “

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

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        return deserialize(input);
    }

    TreeNode *deserialize(istringstream &input) {
        string s;
        if (input >> s) {
            if (s == "#") return nullptr;
            auto res = new TreeNode(stoi(s));
            res->left = deserialize(input);
            res->right = deserialize(input);
            return res;
        }
        return nullptr;
    }
};

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