请实现两个函数,分别用来序列化和反序列化二叉树,不对序列化之后的字符串进行约束,但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#)
二叉树的反序列化(Deserialize)是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。
例如,可以根据层序遍历的方案序列化,如下图:
层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}",再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。
思路1.将二叉树变为字符串就是按照层序遍历就好了,但是我的遍历结果中末尾多了很多空值,但是不影响最终的结果。
2.字符串转为二叉树。就是将上面转字符串时逆 *** 作一下。
将字符串中的元素一次取出来,如果是空就将二叉树对应的字节置为空,但是不将其加入队列中;如果不是空,就加入队列中,并让当前节点的孩子节点赋值为该节点。
代码import java.util.*; public class Solution { String Serialize(TreeNode root) { if(root == null){ return ""; } if(root.left == null && root.right == null){ return "{"+String.valueOf(root.val)+"}"; } Queuedata = new linkedList<>(); ArrayList res = new ArrayList (); data.add(root); int length; int level = 0; boolean flase; while(!data.isEmpty()){ TreeNode cur = data.poll(); if(cur == null){ res.add(-1); continue; } res.add(cur.val); data.add(cur.left); data.add(cur.right); } String str = "{"; for(Integer e:res){ if( e!=-1){ str+=String.valueOf(e.intValue()); }else{ str+="#"; } str+=","; } str.substring(0,str.length()-1); str+="}"; return str; } TreeNode Deserialize(String str) { if(str.length() == 0){ return null; } int l =str.length(); str = str.substring(1,l-1);//截取字符串 String[] data = str.split(","); Queue queueData = new linkedList<>(); int n = data.length; TreeNode root = new TreeNode(Integer.parseInt(data[0])); queueData.add(root); for(int i = 1;i 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)