HelloKenLee

Leetcode 297 Serialize and Deserialize Binary Tree 解题报告

Posted on By KenLee

题目信息

题目: 297. Serialize and Deserialize Binary Tree
难度: Hard
正确率: 32.2%
问题描述:

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.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ 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.

相关题目:449. Serialize and Deserialize BST

问题分析

  问题的大意是说对于一棵普通的二叉树,如何把它序列化成一个字符串,而对于已经序列化后的二叉树字符串,如何反序列化回一个二叉树。要求是尽可能的少占用空间而且要求序列化后的二叉树一定能反序列化回去,结构和数据都不能够丢失。

解题思路

  这个问题的求解思路无非两点:1. 如何把二叉树型结构转成线性结构? 2. 如何把节点值转成字符串?

  如何把二叉树型结构转成线性结构: 这让我想起了很久以前在SOJ上做的一个问题,就是说要把一个二叉树还原,必须要有其中序遍历结果+前序或后序其中一种结果。不过事实上,对于一颗二叉树的任何一个非空节点,我们存储他的所有左右儿子的值,不管其儿子是否为空,这样我们只需要前序遍历的结果就能还原一个二叉树。或者我们把先序遍历叫做BFS或者层次遍历更为准确。

  如何把节点值转成字符串: 因为题目给出的二叉树其数据为int,因此一个很普通的思路就是直接把他转成字符串。比如,把1234->"1234", 把-256->"-256"。这样子做的好处是序列化后的二叉树有一定的可读性。c++11后也提供了相应的转化函数比如:stoi()itos()。然而这真的是比较优化的解决方法吗? 从时间上来说,这样子转化要做常数时间的乘法和加法;从空间上来说,这样子存储的长度取决于整数的长短,最长是INT_MIN,占11位;从复杂度的来说,这种处理方法除了处理数字以外,还需要约定分割符,比如, 或者 # 或者 _等等。
  要插入分隔符的原因是我们存的数据是不定长的,假设我们采用定长的方式存储,我们就无需插入分割符。因为长度就是天然的分隔符。一个比较优化的解决方法是,一个int占4个byte,一个char占1个byte,因此我们可以直接用4个char来表示一个int。但是,我们还要区分该节点是不是空节点,因此我们需要多一个char来存储。那么对于一个二叉树节点,我们把其序列化为5个char

  一个比较好用的技巧是,对于一个节点的int值,我们用一个char*指针来先后访问其0,1,2,3位,相当于把一个int分成4个8位的二进制数,并把该二进制数对于的ascii码字符存入结果字符串(尽管单个字符没实际意义)。同样的,对于一个字符串,我们每5位,每5位处理,用一个int*指针来访问,就能直接完成转换,而不用增加额外的函数。

  解决指针对齐问题: 上面的解决方法看上去很美好,但是事实上我们因为需要5个char才能表示一个二叉树节点,因此在某些环境上可能会报指针未对齐的运行时错误(比如Leetcode的辣鸡环境)。也很有道理,毕竟我们产生出来的字符串长度是5N个byte,而使用int*访问最好是4N个byte长度。关于这个问题,我想出了三个解决方案:

  1. 手写转换函数,也就是对于表示一个节点的5个char,我们通位运算<<&来转成一个int。因为是位运算,因此在时间上也很快。
  2. 使用缓存。把5个char中的后四位表示int的值通过memcpy()函数拷贝到缓存char buffer[4]中,这样在buffer中就是4byte对齐的,可以直接通过int访问。
  3. 新建一个结构体比如下,包含一个char和一个int。结构体的长度为5byte,然后我们使用node* a访问,a->val来取值。
	struct node{
		char flag;
		int val;
	}

  后面的实现采用第二种方法,因为写起来最短。

结果分析

  • 时间复杂度: O(N),时间复杂度就是进行广度优先搜索的时间,N为二叉树的节点数。
  • 空间复杂度: O(N),采用队列来进行广度优先搜索,其最坏情况下是队列中存有所有节点的指针,复杂的为O(N)。还有就是序列化后的字符串长度,很明显,其长度为5N,也就是O(N),其余空间使用均为常数。因此总的复杂的为O(N)。
  • 通过时间: 22ms
  • 排名: Beats 99.79% submissions. (截止至提交时间)

主要数据结构和方法

  • struct TreeNode: 二叉树数据结构
  • string serialize(TreeNode* root): 把二叉树转换成字符串函数
  • TreeNode* deserialize(string data): 把一个字符串转换成二叉树,返回根节点
  • queue<TreeNode*> que: 用于做先序遍历的队列
  • TreeNode* processNode(unsigned char* &cptr,queue<TreeNode*> &que): 把字符串中的5个byte数据转化成一个二叉树节点

源代码

/**
 * 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) {
        string res;
        //BFS队列
        queue<TreeNode*> que;
        //根节点压入队列
        que.push(root);
        //
        char zeros[5]={0};
        //BFS
        while(!que.empty()){
            TreeNode* now=que.front();
            que.pop();
            if(now!=nullptr){
                //儿子节点压入队列
                que.push(now->left);
                que.push(now->right);
                //序列化该节点
                char* tmp=(char*)&(now->val);
                res.push_back((char)1);
                res.append(tmp,4);
            }else{
                //序列化NULL
                res.append(zeros,5);
            }
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<TreeNode*> que;
        unsigned char* cptr=(unsigned char*)data.c_str();
        const unsigned char* bound=(unsigned char*)data.c_str()+data.size();
        //处理根节点
        TreeNode* root=processNode(cptr,que);
        //处理剩下的节点
        while(cptr<bound){
            TreeNode* now=que.front();
            que.pop();
            now->left=processNode(cptr,que);
            if(cptr>=bound)
                break;
            now->right=processNode(cptr,que);
        }
        return root;
    }
private:
    char buffer[4];
    TreeNode* processNode(unsigned char* &cptr,queue<TreeNode*> &que){
        TreeNode *res;
        if((*cptr)==0){
            res=nullptr;
        }else{
            memcpy(buffer,cptr+1,4);
            res=new TreeNode(*(int*)(cptr+1));
            que.push(res);
        }
        cptr+=5;
        return res;
    }
};