哪个网站可以做信用社的题,做加盟网站哪个最好,网站下载端口建设,厦网站建设培训学校题目
请实现两个函数#xff0c;分别用来序列化和反序列化二叉树#xff0c;不对序列化之后的字符串进行约束#xff0c;但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指#xff1a;把一棵二叉树按照某种遍历方式的结…题目
请实现两个函数分别用来序列化和反序列化二叉树不对序列化之后的字符串进行约束但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改序列化的结果是一个字符串序列化时通过 某种符号表示空节点# 二叉树的反序列化(Deserialize)是指根据某种遍历顺序得到的序列化字符串结果str重构二叉树。
例如可以根据层序遍历的方案序列化如下图: 层序序列化(即用函数Serialize转化)如上的二叉树转为{1,2,3,#,#,6,7}再能够调用反序列化(Deserialize)将{1,2,3,#,#,6,7}构造成如上的二叉树。
当然你也可以根据满二叉树结点位置的标号规律来序列化还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束所以欢迎各种奇思妙想。
数据范围节点数 0n≤100树上每个节点的值满足 0≤val≤150
要求序列化和反序列化都是空间复杂度 O(n)时间复杂度 O(n)
示例1
输入{1,2,3,#,#,6,7}
返回值{1,2,3,#,#,6,7}
说明如题面图
示例2
输入{8,6,10,5,7,9,11}
返回值{8,6,10,5,7,9,11} 解答
源代码
import java.util.*;
/*
public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}}
*/
public class Solution {public StringBuffer str new StringBuffer();public int index 0;public String Serialize(TreeNode root) {if (root null) {str.append(#);return str.toString();}str.append(root.val).append(,);Serialize(root.left);Serialize(root.right);return str.toString();}public TreeNode Deserialize(String str) {if (str.charAt(index) #) {index;return null;}int val 0;while (str.charAt(index) ! ,) {val val * 10 str.charAt(index) - 0;index;}TreeNode root new TreeNode(val);if (index str.length()) {return root;} else {index;}root.left Deserialize(str);root.right Deserialize(str);return root;}
}
总结
序列化就是将二叉树转换为字符串可以按照自己设定的规则这里我选择了前序遍历将遍历得到的节点值添加进字符串中字符串中不同节点值之间以 , 连接空节点以 # 表示反序列化则是通过字符串转换为二叉树。
