297. Serialize and Deserialize Binary Tree

Tags: Hard Tree

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

---

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

---

在《树——二叉树的构建》里面进行了总结。这道题其实就是一本通-1340：【例3-5】扩展二叉树的一个翻版，只不过现在需要自己手动实现扩展二叉树的输出，并且有一个很重要的不同点，相比于一本通1340里的单个字母，二叉树里的节点存储的数值可能不止一位，所以需要用一个特殊的标记符号#来对数据进行分隔，用.代表空节点。

序列化部分采用前序遍历的递归实现，注意需要去掉末尾的#符号，用pos记录处理到序列的哪个位置，每次指向第一个数字，然后递归构建左右子树。

/**
 * 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        string res;
        if (!root) return res;

        preorderTraversal(root, res);

        return res.substr(0, res.size() - 1);
    }

    void preorderTraversal(TreeNode *root, string & res)
    {
        if (!root) {
            res += ".#"; return;
        }

        res += to_string(root -> val);
        res.push_back('#');
        preorderTraversal(root -> left, res);
        preorderTraversal(root -> right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;

        int pos = 0;
        TreeNode *root;
        build(data, root, pos);
        return root;
    }

    void build(string & data, TreeNode *&root, int &pos)
    {
        int nextPos = data.find("#", pos);
        if (nextPos == string::npos) {
            string tmp = data.substr(pos);
            if (tmp.size() == 1 && tmp[0] == '.') root = NULL;
            else root = new TreeNode(stoi(tmp));
            return;
        }

        string tmp = data.substr(pos, nextPos - pos);
        pos = nextPos + 1;
        if (tmp[0] == '.') root = NULL;
        else {
            root = new TreeNode(stoi(tmp));
            build(data, root -> left, pos);
            build(data, root -> right, pos);
        }
    }
};

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