面试题37

请实现两个函数，分别用来序列化和反序列化二叉树。

示例: 

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

Solutions

1. preorder traversal with recursion

/**
 * 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:
    void serialize(TreeNode * root, string & s) {
        if (!root)
            s.push_back(',');
        else {
            s += to_string(root->val) + ",";
            serialize(root->left, s);
            serialize(root->right, s);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        serialize(root, res);
        return res;
    }
    int deserialize(string & s, int start, TreeNode ** root) {
        if (s[start] == ',') {
            *root = nullptr;
            return start + 1;
        }
        else {
            int end = start;
            while (s[end] != ',') end++;
            TreeNode * cur = new TreeNode(stoi(s.substr(start, end - start)));
            *root = cur;
            end = deserialize(s, end + 1, &(cur->left));
            end = deserialize(s, end, &(cur->right));

            return end;
        }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode * root;
        deserialize(data, 0, &root);
        return root;
    }
};

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

1. level order traversal with queue

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            root = q.front(); q.pop();
            if (root) {
                res += to_string(root->val) + ",";
                q.push(root->left);
                q.push(root->right);
            }
            else
                res.push_back(',');
        }

        return res;
    }

    inline TreeNode * node(string & s, int & cur) {
        TreeNode * root = nullptr;
        if (s[cur] != ',') {
            int st = cur;
            while (cur < s.size() && s[cur] != ',')
                cur++;
            root = new TreeNode(stoi(s.substr(st, cur - st)));
        }
        cur++;

        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int cur = 0;
        queue<TreeNode *> q;
        TreeNode * root, * head;
        q.push(root = head = node(data, cur));

        while (cur < data.size()) {
            root = q.front(); q.pop();
            if (!root) continue;
            root->left = node(data, cur);
            root->right = node(data, cur);
            q.push(root->left);
            q.push(root->right);
        }

        return head;
    }
};