【LeetCode】297. 二叉树的序列化与反序列化（同剑指Offer37）

一、题目

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

二、解决

1、BFS 【迭代】

思路：

本质是二维数据与一维线性数据的相互转化，更具体转换过程请查看参考1。下面简单概括一下过程：

序列化

可以先看【LeetCode】算法模板与刷题方法小结（不断更新中）的 3、BFS 模板代码，消化修改后就是序列化的版本。

这里修改动作就是判断是否为null，if yes, then res.append(“null”)，else 正常添加左右子节点。

反序列化

这里就是将序列化后的一维线性数据重建成二叉树的过程。

首先将字符串转换为字符数组，然后逐个将其转化为TreeNode，将其插入二叉树中。

核心是判断，若字符为null，不管，因为构造函数中一般是左右子树为空，具体可见下面补充；否则，则按序插入左右子节点。

// 补充：二叉树定义 public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val) { this.val = val; this.left = null; this.right = null; } }

代码：

public class Codec { public String serialize(TreeNode root) { if(root == null) return "[]"; StringBuilder res = new StringBuilder("["); Queue<TreeNode> 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(); } 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])); Queue<TreeNode> 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; } }

时间复杂度： $O(n)$ 空间复杂度： $O(n)$

2、DFS

版本1：递归 【先序遍历】

思路：

序列化

先序遍历的简单改动，比较简单。

反序列化

本质是对一个队列，使用递归的方式建二叉树的过程。(尚未完全理解，需要进一步消化)

代码：

public class Codec { public String serialize(TreeNode root) { if (root == null) return "#"; return root.val + "," + serialize(root.left) + "," + serialize(root.right); } public TreeNode deserialize(String data) { Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(","))); return helper(queue); } private TreeNode helper(Queue<String> queue) { String s = queue.poll(); if (s.equals("#")) return null; TreeNode root = new TreeNode(Integer.valueOf(s)); root.left = helper(queue); root.right = helper(queue); return root; } }

时间复杂度： $O(n)$ 空间复杂度： $O(n)$

版本2：迭代

思路：

序列化

对【LeetCode】算法模板与刷题方法小结（不断更新中）的6.2 迭代版中的非递归先序遍历模板进行简单改动即可。

反序列化

对先序遍历的一维线性结果表示进行解码，重建成二叉树。

具体过程如下： Step 1：将字符串转换为字符数组strArray，再初始化为双端队列，其功能与栈相同。 Step 2：不断遍历strArray，新的节点连接到左子树上，并将节点入栈，直至遇到null Step 3：栈抛出一个节点pre，然后遍历到strArray的下一个节点cur，将cur连接到pre的右子树上，即pre.right = cur。 Step4：然后回到Step 1，继续循环。

代码：

public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); TreeNode x=root; Deque<TreeNode> stack = new LinkedList<>(); while (x!=null || !stack.isEmpty()) { if (x!=null) { sb.append(String.valueOf(x.val)); sb.append(' '); stack.push(x); x = x.left; } else { sb.append("null "); x = stack.pop(); x = x.right; } } return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.length() == 0) return null; String[] node = data.split(" "); int n = node.length; Deque<TreeNode> stack = new LinkedList<>(); TreeNode root = new TreeNode(Integer.valueOf(node[0])); TreeNode x = root; stack.push(x); int i=1; while (i<n) { while (i<n && !node[i].equals("null")) { x.left = new TreeNode(Integer.valueOf(node[i++])); x = x.left; stack.push(x); } while (i<n && node[i].equals("null")) { x = stack.pop(); i++; } if (i<n) { x.right = new TreeNode(Integer.valueOf(node[i++])); x = x.right; stack.push(x); } } return root; } }

时间复杂度： $O(n)$ 空间复杂度： $O(n)$

三、参考

1、面试题37. 序列化二叉树（层序遍历 BFS ，清晰图解） 2、二叉树的序列化与反序列化 3、Easy to understand Java Solution 4、Clean Java Solution 5、Short and straight forward BFS Java code with a queue 6、Recursive DFS, Iterative DFS and BFS