题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
    //序列化
    //我采用层序遍历来序列化这棵树
    //并且自动把这颗树补成完全二叉树
    int index=0;//定义为全局变量
    char*str=new char[10000];//因为题目中说了节点数<=100，所以开一个10000的数组肯定够了
    int data[10000];
    char* Serialize(TreeNode *root) {    
        if(root==NULL)//如果是空树直接返回即可
            return str;
        queue<TreeNode*> que;//申请一个层序遍历所需的队列
        que.push(root);
        while(!que.empty()){//当队列非空时
            TreeNode*node=que.front();//弹出队头元素
            que.pop();
            if(!node){//如果node为空
                str[index++]='#';
                data[index-1]=-1;
                que.push(NULL);//补成完全二叉树
                que.push(NULL);
                if(index==10000)//补成完全二叉树，及时break，如果不加这条语句会无限循环（该语句没别的含义仅仅为了停止循环）
                    break;
            }
            else{
                str[index++]=char(node->val+48);
                data[index-1]=node->val;
                que.push(node->left);
                que.push(node->right);
            }
        }
        for(int i=0;i<index;i++)
            cout<<str[i]<<" ";
        return str;
    }
    //反序列化
    //思路为由str数组构造一个同样大小的节点指针数粗
    TreeNode* Deserialize(char *str) {
        if(index<=0)//数组的大小<=0说明为空树
            return NULL;
        TreeNode*arr[10000];
        //构造节点指针数组
        for(int i=0;i<index;i++){
            if(data[i]!=-1){
                arr[i]=new TreeNode(data[i]);
            }
            else arr[i]=NULL;
        }
        //层序遍历序列化的结果数组有这样的特点，如果某个几点在数组中的下标为i那么他的左右孩子的下标若存在则为2*i+1和2*i+2
        for(int i=0;i<index;i++){
            if(arr[i]==NULL)
                continue;
            if(2*i+1<index){//左孩子如果存在
                arr[i]->left=arr[2*i+1];
            }
            else{//说明是最后一层的叶子结点，节点值没有保存到数组中
                arr[i]->left=NULL;//直接为空
            }
            if(2*i+2<index){
                arr[i]->right=arr[2*i+2];
            }
            else 
                arr[i]->right=NULL;
        }
        return arr[0];//返回根节点
    }
};