序列化二叉树

序列化二叉树

题目链接
方法1：层序遍历
知识点：队列
方法：队列
所谓层序遍历，就是从上到下依次遍历节点，将每个节点的左右儿子加入到队列中，然后依次出队和入队，遍历得到的顺序就是层序遍历，我们用队列来模拟，具体可以看代码的注释，这里先给出图示

例如这棵树中，我们先将根节点[1]加入到队列中，这样就是

然后我们弹出队头，查看队头连接的两个子节点，发现是2，3，于是分别加入队列

此时我们继续弹出队头2，查看队头连接的两个子节点，发现无子节点，就不用加入队列，类似的，继续看3，我们发现其有4，5作为子节点，于是加入队列

类似的，只要依次弹出队头，查看其连接的子节点，如果有就加入到队列中，否则就查看下一个，最后弹出队列的顺序就是层序序列了。

这里是将二叉树序列化的代码

    char* Serialize(TreeNode *root) {    
        queue<TreeNode*> q;//创建一个队列
        q.push(root);//将根加入队列中
        string s;//用string来记录序列化后的二叉树
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();//将队头弹出
            if (node == NULL) {//如果发现是空节点，说明要加入'#'
                s.push_back('#');
            } else {
                s += to_string(node->val);//to_string函数可以将数值转换成字符串形式
                q.push(node->left);
                q.push(node->right);
                //然后将左右儿子加入到队列中去
            }
            s.push_back('!');//别忘了在每个值结束加入'!'
        }
        char *res = new char[s.size() + 1];
        strcpy(res, s.c_str());
        //最后要返回的是char数组类型，所以要将string转换为char数组
        return res;
    }

然后就是反序列化二叉树，我们只要将字符串反过来模拟一遍就可以重构二叉树了

    TreeNode* Deserialize(char *str) {
        string s(str);
        if (s[0] == '#') {
            //这是一个特殊情况判断，当原序列为空的时候，我们需要返回空指针
            return NULL;
        }
        queue<TreeNode*> q;
        TreeNode *root = new TreeNode(atoi(s.c_str()));//创造根节点
        s = s.substr(s.find('!') + 1);
        q.push(root);
        while (!q.empty() && !s.empty()) {
            TreeNode *node = q.front();
            q.pop();
            //加入左子树
            if (s[0] == '#') {
                node->left = NULL;
                s = s.substr(2);
            } else {
                node->left = new TreeNode(atoi(s.c_str()));
                q.push(node->left);
                s = s.substr(s.find('!') + 1);
            }
            //加入右子树
            if (s[0] == '#') {
                node->right = NULL;
                s = s.substr(2);
            } else {
                node->right = new TreeNode(atoi(s.c_str()));
                q.push(node->right);
                s = s.substr(s.find('!') + 1);
            }
        }
        return root;//返回根
    }

所以最终版本就是这样的
时间复杂度：由于每个点都被遍历到一次，所以时间复杂度是O(n)
空间复杂度：没有引入额外空间，空间复杂度是O(1)

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        queue<TreeNode*> q;//创建一个队列
        q.push(root);//将根加入队列中
        string s;//用string来记录序列化后的二叉树
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();//将队头弹出
            if (node == NULL) {//如果发现是空节点，说明要加入'#'
                s.push_back('#');
            } else {
                s += to_string(node->val);//to_string函数可以将数值转换成字符串形式
                q.push(node->left);
                q.push(node->right);
                //然后将左右儿子加入到队列中去
            }
            s.push_back('!');//别忘了加入'!'
        }
        char *res = new char[s.size() + 1];
        strcpy(res, s.c_str());
        //最后要返回的是char数组类型，所以要将string转换为char数组
        return res;
    }
    TreeNode* Deserialize(char *str) {
        string s(str);
        if (s[0] == '#') {
            //这是一个特殊情况判断，当原序列为空的时候，我们需要返回空指针
            return NULL;
        }
        queue<TreeNode*> q;
        TreeNode *root = new TreeNode(atoi(s.c_str()));//创造根节点
        s = s.substr(s.find('!') + 1);
        q.push(root);
        while (!q.empty() && !s.empty()) {
            TreeNode *node = q.front();
            q.pop();
            //加入左子树
            if (s[0] == '#') {
                node->left = NULL;
                s = s.substr(2);
            } else {
                node->left = new TreeNode(atoi(s.c_str()));
                q.push(node->left);
                s = s.substr(s.find('!') + 1);
            }
            //加入右子树
            if (s[0] == '#') {
                node->right = NULL;
                s = s.substr(2);
            } else {
                node->right = new TreeNode(atoi(s.c_str()));
                q.push(node->right);
                s = s.substr(s.find('!') + 1);
            }
        }
        return root;//返回根
    }
};

方法2：先序遍历
知识点：递归
对于一棵树，先遍历根节点，然后再遍历其左子树和右子树，遍历顺序就是先序遍历了，递归遍历即可
时间复杂度：由于每个点都被遍历到一次，所以是O(n)
空间复杂度：没有引入额外空间，空间复杂度是O(1)

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if (root == NULL) return "#";//如果是空节点，就加上"#"
        string res = to_string(root->val);
        res.push_back('!');
        char *left = Serialize(root->left);
        char *right = Serialize(root->right);//递归遍历左右子节点
        //接下来都是将当前节点加入到序列当中的操作
        char *node = new char[strlen(left) + strlen(right) + res.size()];
        strcpy(node, res.c_str());
        strcat(node, left);
        strcat(node, right);
        return node;
    }
    TreeNode* remake(char *&s) {//这里用引用操作，方便传值
        if (*s == '#') {
            ++ s;
            return NULL;
        }
        int val = 0;
        while (*s != '!') {
            val = val * 10 + *s - '0';
            ++ s;
        }
        ++ s;
        TreeNode *node = new TreeNode(val);//构造当前节点
        node->left = remake(s);
        node->right = remake(s);
        return node;
    }
    TreeNode* Deserialize(char *str) {
        return remake(str);
    }
};