第二十五题
代码比较长 利用层序遍历 保存序列以及还原序列
注意：字符表示的范围；哪些算是空节点？如何表示和判断空节点？
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    // 用来表示当前结点不是一个结点 但因为需要留出二叉树的位置 而填充的（表示空）
    TreeNode* notnode=new TreeNode(-1);
    
    char* Serialize(TreeNode *root) {    
        // 用层序比较简单
        // 先知道深度，之后 根据深度对应深度的满二叉树的序列
        // 还原就是将满二叉树序列 恢复成树
        
        // 知道深度 2^深度-1就是满二叉树的结点个数
        int depth = getdepth(root);
//         cout<<depth<<endl;
        // ret_ans用来存储返回的序列
        // 长度为 2^深度+1
        // 第一个是空 为了数组访问直接从1开始
        // 最后一个是自己填充的151 因为数据表示在0-150 之间 不超过151  151就用来记录ret_ans这个序列结束了
        char *ret_ans=new char[int(pow(2,depth)+1)];
        
         // 用于层次遍历 保存后续结点的队列
        queue<TreeNode *> p;
        // 第一次先把根节点放进去
        p.push(root);
        
        // 记录当前在第几层从1开始计算
        int level=1;
        
        // 层次遍历 如果队列不是空，则继续往下遍历
        // 从第一层开始  处理完深度的树
        while( level<=depth ){
            // length表示这一层存有几个 决定了之后要遍历的次数
            int length = p.size();
            int k=0;
            
            // 和之字形套路一样 只用队列中的length个
            while(length--)
            {
                // 如果说 这个点是我自己预留出来的空节点 也就是val=-1
                if(p.front()->val==-1){
                    p.pop();
                    // char # 表示为空 在第二个要求 转换回二叉树的时候要用到
                    ret_ans[int(pow(2,level-1))+k] = '#';
                    k++;
                    // 每一个空节点 会产生连个子空节点
                    p.push(notnode);
                    p.push(notnode);
                    continue;
                }
                
                // 访问当前结点
                TreeNode* thisnode = p.front();
                p.pop();
                
                // 把该节点的数据存到序列中
                // 每个点的位置是：2^(当前level) +k
                // 这里为什么要-128 是因为 char类型表示的是[-128,128] 但是范围是[0,150] 后面太大的数会导致溢出
                // 所以减去128 并在还原的时候加上128
                ret_ans[int(pow(2,level-1))+k]=char(thisnode->val-128);
                k++;
                // 如果左右孩子还有 就push进队列（记住，此时所有入得队列 都代表是下一层的）
                // 反之，如果左右孩子是空 就push notnode （用来保证所传递的序列 位置上是有东西的）
                if(thisnode->left!=NULL)
                    p.push(thisnode->left);
                else
                    p.push(notnode);
                if(thisnode->right!=NULL)
                    p.push(thisnode->right);
                else
                    p.push(notnode);
            }
            
            // 到下一层处理
            level++;
        }
        // 可以取消注释 看一眼所有保存到序列的值
//         for (int i =1;i<int(pow(2,depth));i++){
//             cout<<i<<ret_ans[i]<<" ";
//         }
        // 在最后一个位置插入151 表示 序列结束
        int a=151;
        ret_ans[int(pow(2,depth))] = char(a);
        return ret_ans;
    }
    
    // 序列转化为二叉树
    TreeNode* Deserialize(char *str) {
        // 结果
        TreeNode *tree_ans;
        // 统计长度 决定了后面创建树的循环的次数
        int length=0;
        for(int i =0;;i++)
        {
            // 151 在这里用上了 当数字是151 表示结束了
            int a=151;
            if(str[i]!=char(a))
                length++;
            else
                break;
        }
        // 因为str第0个位置空的 所以真正的长度是length-1
        // cout<<length-1<<endl;
        // 如果说 长度为0 返回空树
        if(length-1 == 0)
            return NULL;
        
        // 开始构造树 每个树都要创建出一个结点
        tree_ans=new TreeNode(0);
        // 层次遍历的队列
        queue<TreeNode*> q;
        TreeNode* temp;
        q.push(tree_ans);
        
        // 循环次数 就是看传来的序列有几个字 也代表了 树有几个结点
        for (int i =1 ; i<length ; i++)
        {
            // 获取要处理的结点
            temp=q.front();
            q.pop();
            // 如果说不是# 代表原来是结点 要进行处理
            if(str[i]!='#')
            {
                // 下面两个if else 决定了是否有左右孩子，如果有左右孩子 就创建出一个新的树的结点 并放入队列
                // 如果没有左（右）孩子，就push一个空 保证树的位置正确。
                // 通过树父亲结点i的两个孩子分别是 2*i 和 2*i+1 来判断
                if(i*2<=length-1 && str[i*2]!='#')
                {
                    temp->left=new TreeNode(0);
                    q.push(temp->left);
                }
                else
                    q.push(notnode);
                if(i*2+1 <=length-1 && str[i*2+1]!='#')
                {
                    temp->right=new TreeNode(0);
                    q.push(temp->right);
                }
                else
                    q.push(notnode);
                // 还原结点 加上128 因为之前减了128
                temp->val=str[i]+128;
            }
            // 如果字符是# 代表原来是个空节点 让存进来的结点依旧保持为空
            else
            {
                temp=NULL;
                // 一个空节点 下面就会有两个空孩子 放入队列 保证 创建树的正确性
                q.push(notnode);
                q.push(notnode);
            }
                
        }
        return tree_ans;
    }
    
    // 知道深度 递归调用 就不说了
    int getdepth(TreeNode *root){
        int depth=0;
        if(root==NULL)
            return depth;
        int leftdepth=getdepth(root->left);
        int rightdepth = getdepth(root->right);
        depth = leftdepth > rightdepth ? leftdepth:rightdepth;
        return depth+1;
    }
};