局域网内建立网站,90设计网怎么样,怎么添加网站权重,无锡网络推广服务题目
请实现两个函数#xff0c;分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑#xff0c;你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 …题目
请实现两个函数分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示输入输出格式与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。 示例 输入root [1,2,3,null,null,4,5]输出[1,2,3,null,null,4,5] 解题思路 1.题目要求我们实现两个函数分别用来序列化和反序列化二叉树。首先我们来实现序列化二叉树也就是将二叉树的层序遍历变为一个数组那我们就需要用一个StringBuilder res来拼接遍历到的元素还需要一个队列 queue 来按照层序遍历来遍历二叉树首先我们将根节点放入 queue 中当 queue不为null我们就让queue中的元素出队然后判断当前出队元素是否为null若当前出队元素不为null我们就将当前出队元素与“”逗号拼接到 StringBuilder res中然后再将当前出队元素的左右孩子加入队列中。若当前出队元素为 null我们就将 “null”拼接到 queue 中。最后我们将多余的“”删除并且加上“]”,然后返回即可。 2.反序列化的实现有一点复杂我们画图来看 举个例子 实现反序列化我们依旧需要一个队列 queue然后将所给的数组去除逗号后将它保存在数组vals中我们知道层序遍历的第一个元素是二叉树的根节点所以我们先让 vals[0] 入队。同时设置一个变量i 1遍历数组用。 当队列queue不为null时我们让队头元素出列2出列这时 i 指向的元素不为 null 恰好是(2)的左孩子所以我们就要令(2) 的左孩子指向(3),并且让(3)入队。然后我让 i 后移一位 这时 i 指向的元素不为 null 恰好是(2)的右孩子所以我们就要令(2) 的右孩子指向(4),并且让(4)入队。然后我让 i 后移一位 queue不为null我们让队头元素出列3出列这时 i 指向的元素不为 null 恰好是(3)的左孩子所以我们就要令(3) 的左孩子指向(5),并且让(5)入队。然后我让 i 后移一位 这时 i 指向的元素为 null 我们不做任何操作因为(3)的右孩子node.right初始值就为null我直接将 i 后移一位 queue不为null我们让队头元素出列4出列这时 i 指向的元素不为 null 恰好是(4)的左孩子所以我们就要令(4) 的左孩子指向(6),并且让(6)入队。然后我让 i 后移一位 i 指向的元素为 null 我们不做任何操作接将 i 后移一位 queue不为null我们让队头元素出列5出列 i 指向的元素为 null 我们不做任何操作接将 i 后移一位 i 指向的元素为 null 我们不做任何操作接将 i 后移一位 queue不为null我们让队头元素出列6出列 i 指向的元素为 null 我们不做任何操作接将 i 后移一位 i 指向的元素为 null 我们不做任何操作接将 i 后移一位 代码实现
public class Codec {public String serialize(TreeNode root) {if(root null) return [];StringBuilder res new StringBuilder([);QueueTreeNode queue new LinkedList() {{ add(root); }};while(!queue.isEmpty()) {TreeNode node queue.poll();if(node ! null) {res.append(node.val ,);queue.add(node.left);queue.add(node.right);}else res.append(null,);}res.deleteCharAt(res.length() - 1);res.append(]);return res.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data.equals([])) return null;String[] vals data.substring(1, data.length() - 1).split(,);TreeNode root new TreeNode(Integer.parseInt(vals[0]));QueueTreeNode queue new LinkedList() {{ add(root); }};int i 1;while(!queue.isEmpty()) {TreeNode node queue.poll();if(!vals[i].equals(null)) {node.left new TreeNode(Integer.parseInt(vals[i]));queue.add(node.left);}i;if(!vals[i].equals(null)) {node.right new TreeNode(Integer.parseInt(vals[i]));queue.add(node.right);}i;}return root;}
}
测试结果
