题目描述

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

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

样例
你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"

算法1

1 树的中序前序后序遍历都可以访问到所有节点
但是无法得知节点在树的层级位置等信息
如图

但是如果我们使用满二叉树的格式来看待这颗树，不足的位置使用NULL来填充。

那么按照次序的遍历，是可以定位出该节点在树的位置。

2 接下来的问题是如何分割节点以及如何显示节点的数值和null节点
我采取的办法是#分割，N表示null节点，数值则直接转化成字符串即可
示例中的二叉树按照中序遍历转换最终可以转换成如下字符串
“#8#12#2#N#N#6#4#N#N#N#N#”

C++ 代码

/**
 * 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 bfsTree(TreeNode* root,string& s){
        if(root==NULL)  { s+="N#";return; }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* p = q.front(); q.pop();
            if(p==NULL){ s+="N";s+="#";}
            else { s+= to_string(p->val);s+="#";}
            if(p!=NULL){
                q.push(p->left);
                q.push(p->right);
            }
        }

        return;
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans = "#";
        bfsTree(root,ans);
        return ans;
    }

    TreeNode* GetNode(const string& data,int& idx)
    {
        int l = idx; 
        while(data[l]!='#'&& l< data.size()) l++;
        int r =l+1;
        while(data[r]!='#'&& r <data.size()) r++;

        string str = data.substr(l+1,r-l-1);
        idx =r;
        if(str == "N") return NULL;

        int val = atoi(str.c_str());
        TreeNode* p = new TreeNode(val);

        return p;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        cout<<data<<endl;
        int idx = 0;
        TreeNode* head = GetNode(data,idx);
        if(head==NULL) return head;

        queue<TreeNode*> q;
        q.push(head);

        while(!q.empty()){
            TreeNode* p = q.front();q.pop();
            if(p!=NULL){
                p->left = GetNode(data,idx);
                p->right = GetNode(data,idx);
                q.push(p->left);
                q.push(p->right);
            }
        }

        return head;
    }
};

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

我的视频题解空间