题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 先序遍历法

按先序遍历的顺序对数组进行序列化，遇到nullptr记位#，并返回。 反序列化也是按先序遍历的顺序递归，按左中右的顺序进行递归，重建二叉树

class Codec {//两种方法。1.先序遍历
public:
    void dfsBuild(TreeNode* cur, stringstream& ss){//注意！这里ss要加引用，要修改原始ss，这里还得多理解一点
        if(!cur){//遇到空节点就输入#并直接返回
            ss<<'#'<<' ';
            return;
        }
        ss<<to_string(cur->val)<<' ';//将当前节点值输入ss
        dfsBuild(cur->left, ss);
        dfsBuild(cur->right, ss);//递归左右子树，先序遍历的顺序
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return string();//为空直接返回空字符串
        stringstream ss;//定义字节流ss
        dfsBuild(root, ss);//递归根节点
        return ss.str();//返回ss中寸的字符串

    }

    void dfsRebuild(TreeNode* &cur, stringstream& ss){//注意！这里的cur也要加引用，因为要在原root上修改
        string tmp;//定义字符串tmp接受ss中的按空格分开的字符串
        ss>>tmp;
        if(tmp=="#") return;//若遇到#说明是根节点，返回
        cur = new TreeNode(stoi(tmp));//重新定义cur，注意不能直接修改cur->val，因为最初cur定义为空指针，没有val
        dfsRebuild(cur->left, ss);
        dfsRebuild(cur->right, ss);//递归左右根节点
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;//data为空直接返回空指针
        stringstream ss(data);//定义ss接受data字符串
        TreeNode* root = nullptr;//先定义root为空
        dfsRebuild(root, ss);//递归重建根节点
        return root;//返回结果
    }
};

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

2. 层次遍历法

按层次遍历的方法编码解码，其中编码和层次遍历一模一样，主要是解码的时候要注意左右节点要成对出现，为每个节点同时增加左右节点

class Codec {//两个方法。2. 层次遍历
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {//这里就是二叉树的层次遍历
        //两个区别
        //1.使用了stringstream保存结果，个人感觉也可以不用，但是decode最好用
        //2.遇到空节点需要输入一个字符，这里用#
        if(!root) return string();
        stringstream ss;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            auto cur = q.front();q.pop();
            if(!cur) ss<<'#'<<' ';
            else{
                ss<<cur->val<<' ';
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        stringstream ss(data);//将字符串导入stringstream
        string tmp;
        ss>>tmp;//先输出第一个数，为根节点
        TreeNode* root = new TreeNode(stoi(tmp));
        queue<TreeNode*> q({root});//将根节点压入队列
        while(!q.empty()){
            auto cur = q.front();q.pop();//输出队尾为cur
            //注意下面，每次输出要成对出现，一左一右，
            //遇到#就加上空节点，
            //其他情况创建一个新节点，val为当前值，并把新节点压入栈中
            ss>>tmp;
            if(tmp=="#") cur->left = nullptr;
            else{
                cur->left = new TreeNode(stoi(tmp));
                q.push(cur->left);
            }
            ss>>tmp;
            if(tmp=="#") cur->right = nullptr;
            else{
                cur->right = new TreeNode(stoi(tmp));
                q.push(cur->right);
            }
        }
        return root;
    }
};

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