栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法之树的序列化与反序列化

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法之树的序列化与反序列化

剑指 Offer 37. 序列化二叉树

首先明确遍历的方式,先序,中序,后序遍历可能对应着多种二叉树,导致序列化后不可逆,通常还是使用层序遍历。

还有就是明确这道题力扣给的测试用例所代表的树到底是什么,例如[5,2,3,null,null,2,4,3,1,null,null,null,null,null,null],需要注意第8,9个元素3,1是第6个元素2的子节点,而不是第4个元素null的子节点,即不是按照满二叉树的标准来生成序列的,因此不能直接使用满二叉树的父节点与子节点的下标关系来做这道题。

层序遍历

  1. 注意,字符串的操作如果可以使用StringBuilder就尽量使用StringBuilder,会节省很多很多时间
  2. 新建队列也可以使用Queue queue = new LinkedList<>();

简单说说LinkedList和Queue的区别:
LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法 了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用。
因此,其实用Queue会更规范。

public String serialize(TreeNode root) {
        //注意判断根节点是否为空,为空的话直接返回
        if(root==null) return "";
        StringBuilder s=new StringBuilder("");
        //新建一个队列,将根节点入队
        LinkedList q=new LinkedList<>();
        q.add(root);
        //while循环,判断条件是队列是否为空
        while(!q.isEmpty()){
            TreeNode node=q.poll();
            if(node==null){   //节点为空则打印null
                s.append("null ");
            }else{  //节点不为空则添加左右节点,并打印节点值
                //list可以添加空的node,但这个node指向左右孩子以及val值时会报错
                q.add(node.left);
                q.add(node.right);
                s.append(node.val).append(" ");
            }
        }
        return s.toString();
    }

反序列化
有点难想明白

public TreeNode deserialize(String data) {
        data=data.trim();
        String[] a=data.split(" ");
        //注意判断data是否为空
        if(a[0].equals("")) return null;
        TreeNode root=new TreeNode(Integer.parseInt(a[0]));
        //i用于遍历data里的数据,任然需要借助队列来构造二叉树
        int i=1;
        LinkedList q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node=q.poll();
            //如果不是满二叉树,这种方法就不太行
            //int tmp=i*2+1;
            //下面的方法算是妙手,还是多看看记住吧,注意i值的变化
            //不论节点是否为空,i值都会增加,只有遍历到的数不为空时才将其加入队列
            if(!a[i].equals("null")){
                node.left=new TreeNode(Integer.parseInt(a[i]));
                q.add(node.left);
            }
            i++;
            if(i
                node.right=new TreeNode(Integer.parseInt(a[i]));
                q.add(node.right);
            }
            i++;
        }
        return root;
    }

下面为其他人提供的一种反序列化方法,但该方法并不能很好的将数组转化成二叉树,原因就在于前面所说的,力扣通过数组提供的树并不都是按照满二叉树的下标关系来的,因此会出现不完整的转化或者错误的转化

public static TreeNode array2Tree (Integer[] arr){
        if (arr.length < 1){
            return null;
        } else {
            TreeNode root = new TreeNode(arr[0]);
            int i = 0;
            int arrLen = arr.length;
            // 用于bfs
            Deque queue = new LinkedList<>();
            queue.addLast(root);
            while (queue.size() > 0){
                TreeNode treeNode = queue.removeFirst();
                int temp = (i<<1) + 1;   //最大的问题就在这一步
                if (treeNode != null && temp < arrLen){
                    if (arr[temp] != null){
                        treeNode.left = new TreeNode(arr[temp]);
                    }
                    temp++;
                    if (temp < arrLen){
                        if (arr[temp] != null){
                            treeNode.right = new TreeNode(arr[temp]);
                        }
                    }
                    queue.addLast(treeNode.left);
                    queue.addLast(treeNode.right);
                }
                i++;
            }
            return root;
        }
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963990.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号