剑指 Offer 37. 序列化二叉树

LeetCode： 剑指 Offer 37. 序列化二叉树

序列化 >> 树的层序遍历

反序列化 >> 将各个节点存入到 List 中

然后通过 list 的遍历， 双指针 >> slow 记录当前父节点 >> fast 记录当前遍历到的子节点

// 序列化 树 // Encodes a tree to a single string. public String serialize(TreeNode root) { List<String> list = new ArrayList<>(); if(root == null) return list.toString(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode pop = ((LinkedList<TreeNode>) queue).pop(); if(pop == null){ list.add("null"); continue ; } list.add(pop.val + ""); // 左子树 queue.offer(pop.left); // 右子树 queue.offer(pop.right); } } return list.toString(); } // 反序列化 树 // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if("".equals(data) || data == null || "[]".equals(data)) return null; String s = data.substring(1, data.length() - 1); String[] split = s.split(","); if(split.length == 0) return null; List<TreeNode> list = new ArrayList<>(); for (int i = 0; i < split.length; i++) { if(split[i].trim().equals("null")) { list.add(null); continue ; } list.add(new TreeNode(Integer.valueOf(split[i].trim()))); } int slow = 0, fast = 1; while (fast < split.length){ TreeNode node = list.get(slow); if(node != null){ node.left = list.get(fast++); node.right = list.get(fast++); } slow++; } return list.get(0); }

反序列还可以使用队列

队列存放当前层数的父节点

单指针指向当前遍历到的子节点