7 Serialize and Deserialize Binary Tree 序列化及反序列化二叉树

原题网址：http://www.lintcode.com/zh-cn/problem/serialize-and-deserialize-binary-tree/#

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

注意事项

There is no limit of how you deserialize or serialize a binary tree, LintCode will take your output of serialize as the input of deserialize, it won't check the result of serialize.

您在真实的面试中是否遇到过这个题？

Yes

样例

给出一个测试数据样例，二叉树{3,9,20,#,#,15,7}，表示如下的树结构：

我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时，你可以作为输入调试你的代码。

你可以采用其他的方法进行序列化和反序列化。

标签

二叉树雅虎微软优步脸书亚马逊 Bloomberg 领英谷歌

思路：序列化二叉树时用广度优先搜素的方法，设置一个队列保存节点，依次遍历。因为空节点无法插入队列，所以用root代替空节点，这样判断当前节点是否为root就可以判断是有效节点还是空节点了。

注意，该程序结束时字符串尾部会插入多余的‘#’和‘，’，要将这些无效字符删掉。

更新：又测试了下发现NULL可以插入指针队列，emmm……

反序列化：依旧是利用队列的先入先出特性，因为要判断新建立的节点是左节点还是右节点，所以再设置一个bool类型的判断标志。

首先建立根节点，然后遍历字符串，如果当前字符为‘，’就continue；

如果为‘#’就判断新建立的是左节点还是右节点，如果是右节点代表其根节点已经全部挂载完成，此时需要队列出队，在下一个节点上继续挂载，同时标志反转；

否则，当前节点为有效数值，首先将这些字符转换成int型数据，然后new出一个二叉树节点，判断挂载在左侧还是右侧，然后标志反转，若是右侧，队列再出队。

AC代码：

注意空字符串要返回""而不是NULL……

以及，int转string可以用to_string（），但我测试代码时用的VS2010，还不能支持这个函数，所以自己定义了一个。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode * root) {
        
        // write your code here
        if (root==NULL)
    {
        return "";//return NULL出错;
    }
    string result;    
    //result=result+to_string(root->val);
    result=result+int2str(root->val);

    queue<TreeNode *> level;
    level.push(root->left);
    level.push(root->right);
    
    while(!level.empty())
    {
        TreeNode *temp=level.front();
        level.pop();
        if (temp!=NULL)
        {
            //result=result+","+to_string(temp->val);
            result=result+","+int2str(temp->val);
            level.push(temp->left);
            level.push(temp->right);
        }
        else
        {
            result=result+","+"#";
        }    
    }

    int size=result.size();
    int id=size-1;
    while(id>0&&(result[id]=='#'||result[id]==','))
    {
        id--;
    }
    result.resize(id+1);

    return result;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode * deserialize(string &data) {
        // write your code here
        if (data.empty())
    {
        return NULL;
    }

    int size=data.size();
    int i=0;
    int ro=0;//根节点数值;
    while(data[i]!=','&&i<size)
    {
        char tm=data[i];
        ro=ro*10+tm-'0';
        i++;
    }
    TreeNode * root=new TreeNode(ro); 
    
    queue<TreeNode *> level;
    TreeNode *index=root;    
    bool isLeft=true;

    for (;i<size;i++)
    {
        if (data[i]==',')
        {
            continue;
        }
        else if (data[i]=='#')
        {
            if (isLeft)
            {
                //index->left=NULL;
                isLeft=false;
            }
            else
            {
                //index->right=NULL;
                if (!level.empty())
                {
                    index=level.front();
                    level.pop();
                }
                isLeft=true;
            }    
        }
        else
        {
            int val=0;
            while(i<size&&data[i]!=',') //注意不能写成data[i]!=','&&i<size，因为下标可能超出范围;
            {
                char temp=data[i];
                val=val*10+temp-'0';
                i++;
            }
            
            TreeNode * tempNode=new TreeNode(val);
            level.push(tempNode);
            if (isLeft)
            {
                index->left=tempNode;
                isLeft=false;
            }
            else
            {
                index->right=tempNode;
                if (!level.empty())
                {
                    index=level.front();
                    level.pop();
                }
                isLeft=true;
            }    
        }        
    }
    return root;
    }
    
    
    string int2str(int &i)
{
    string str;
    stringstream stream;
    stream<<i;
    str=stream.str();//stream>>str;
    return str;
}

};

原来的代码……留个纪念。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode * root) {
        
        // write your code here
        if (root==NULL)
    {
        return "";
    }
    string result;    
    //result=result+to_string(root->val);
    result=result+int2str(root->val);

    queue<TreeNode *> level;
    if (root->left==NULL&&root->right!=NULL)
    {
        level.push(root);
        level.push(root->right);
    }
    else if (root->left!=NULL&&root->right==NULL)
    {
        level.push(root->left);
        level.push(root);
    }
    else if (root->left!=NULL&&root->right!=NULL)
    {
        level.push(root->left);
        level.push(root->right);
    }
    
    while(!level.empty())
    {
        TreeNode *temp=level.front();
        level.pop();
        if (temp!=root)
        {
            //result=result+","+to_string(temp->val);
            result=result+","+int2str(temp->val);

            if (temp->left!=NULL&&temp->right!=NULL)
            {
                level.push(temp->left);
                level.push(temp->right);
            }
            else if (temp->left==NULL&&temp->right!=NULL)
            {
                level.push(root);
                level.push(temp->right);
            }
            else if (temp->left!=NULL&&temp->right==NULL)
            {
                level.push(temp->left);
                level.push(root);
            }
            else 
            {
                level.push(root);
                level.push(root);
            }
        }
        else
        {
            result=result+","+"#";
        }    
    }

    int size=result.size();
    int id=size-1;
    while(id>0&&(result[id]=='#'||result[id]==','))
    {
        id--;
    }
    result.resize(id+1);

    return result;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode * deserialize(string &data) {
        // write your code here
        if (data.empty())
    {
        return NULL;
    }

    int size=data.size();
    int i=0;
    int ro=0;//根节点数值;
    while(data[i]!=','&&i<size)
    {
        char tm=data[i];
        ro=ro*10+tm-'0';
        i++;
    }
    TreeNode * root=new TreeNode(ro); 
    
    queue<TreeNode *> level;
    TreeNode *index=root;    
    bool isLeft=true;

    for (;i<size;i++)
    {
        if (data[i]==',')
        {
            continue;
        }
        else if (data[i]=='#')
        {
            if (isLeft)
            {
                //index->left=NULL;
                isLeft=false;
            }
            else
            {
                //index->right=NULL;
                if (!level.empty())
                {
                    index=level.front();
                    level.pop();
                }
                isLeft=true;
            }    
        }
        else
        {
            int val=0;
            while(i<size&&data[i]!=',') //注意不能写成data[i]!=','&&i<size，因为下标可能超出范围;
            {
                char temp=data[i];
                val=val*10+temp-'0';
                i++;
            }
            
            TreeNode * tempNode=new TreeNode(val);
            level.push(tempNode);
            if (isLeft)
            {
                index->left=tempNode;
                isLeft=false;
            }
            else
            {
                index->right=tempNode;
                if (!level.empty())
                {
                    index=level.front();
                    level.pop();
                }
                isLeft=true;
            }    
        }        
    }
    return root;
    }
    
    
    string int2str(int &i)
{
    string str;
    stringstream stream;
    stream<<i;
    str=stream.str();//stream>>str;
    return str;
}

};