前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LintCode-7二叉树的序列化和反序列化

LintCode-7二叉树的序列化和反序列化

作者头像
悠扬前奏
发布2019-05-28 20:32:48
6070
发布2019-05-28 20:32:48
举报
文章被收录于专栏:悠扬前奏的博客

题目

描述

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

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

样例

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

代码语言:javascript
复制
  3
 / \
9  20
  /  \
 15   7

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

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

解答

思路

基础题。 开始忘了Queue类。手动写字符串数组“弹出”的功能,很麻烦。查到Queue类就能很好的解决这个问题了。

代码

代码语言:javascript
复制
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
class Solution {
    /**
     * 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.
     */
    public String serialize(TreeNode root) {
        // write your code here
        // 若根节点为空,返回“#,”
        if(root == null)
            return "#,";
        // 新建StringBudffer,存储节点值
        StringBuffer sb = new StringBuffer(root.val+",");
        // 递归左子树
        sb.append(serialize(root.left));
        // 递归右子树
        sb.append(serialize(root.right));
        // 返回StringBuffer的字符串值
        return sb.toString();
    }
    
    /**
     * 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.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        // 将在字符串按照','拆开成字符串数组
        String[] ss = data.split(",");
        // 用字符串数组构建字符串队列
        Queue<String> q = new LinkedList<String>();
        for(int i = 0; i < ss.length; i++){
            q.add(ss[i]);
        }
        // 递归生成二叉树
        return preOrder(q);
    }
    
    private TreeNode preOrder(Queue<String> q){
        // “弹出”队列下一个字符串
        String val = q.poll();
        // 如果值为'#'说明是空结点
        if(val.equals("#")) return null;
        // 如果值不为'#',用该值的整型值构建节点
        TreeNode node = new TreeNode(Integer.valueOf(val));
        // 遍历构建节点左子树
        node.left = preOrder(q);
        // 遍历构建节点右子树
        node.right = preOrder(q);
        // 返回节点
        return node;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.07.18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
    • 描述
      • 样例
      • 解答
        • 思路
          • 代码
          相关产品与服务
          文件存储
          文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用,可实现对现有应用的无缝集成;按实际用量付费,为您节约成本,简化 IT 运维工作。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档