一、题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思考
从我们这里看到的题目要求是将一颗二叉树能够序列化，并还能够将其反序列化成二叉树。也就是说我们需要保持 null 值来标识某个节点是否还有子节点（第一点要求），第二点要求：序列化的时候我们使用 BFS，三种遍历方式，前、中、后的选择哪个会更好，前序遍历，因为我们一开始就知道了 root 节点，会方便加速我们的序列化和反序列化，万事开头难嘛。
序列化->
反序列化->可举例如下图：
三、代码实现
利用 BFS 实现的
class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ this.val = x; } } // Encodes a tree to a single string. public String serialize(TreeNode root) { //第一步：边界特殊值处理 if (root == null){ return ""; } //第二步：BFS搜索，遍历放到队列中 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); //第三步：将BFS结果进行封装，并处理好边界的符号 StringBuilder sb = new StringBuilder(); sb.append("["); //第四步：中序遍历，进行节点值的处理 while(!queue.isEmpty()){ TreeNode node = queue.poll(); if (node != null){ sb.append(node.val).append(","); queue.offer(node.left); queue.offer(node.right); }else{ sb.append("null,"); } } sb.deleteCharAt(sb.length() - 1); sb.append("]"); return sb.toString(); }
// Decodes your encoded data to tree. public TreeNode deserialize(String data) { //第一步如果字符串为空，则返回null if (data == ""){ return null; } //第二步：将字符串构建成数组 String varStr= data.substring(1,data.length()-1); String [] arrStr= varStr.split(","); //第三步：构建root节点，因为我们是前序遍历 TreeNode root = new TreeNode(Integer.valueOf(arrStr[0])); //第四步：队列遍历来BFS获取每个节点应该存放的节点值 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; //第五步：将数组的值进行构造节点并为下一轮队列遍历做准备 while(!queue.isEmpty() && i <arrStr.length){ TreeNode node = queue.poll(); if (!arrStr[i].equals("null")){ node.left = new TreeNode(Integer.valueOf(arrStr[i])); queue.offer(node.left); } i++; if (!arrStr[i].equals("null")){ node.right = new TreeNode(Integer.valueOf(arrStr[i])); queue.offer(node.right); } i++; } return root; }
复制代码
复杂度分析：
时间复杂度 O(N)： N 为二叉树的节点数，层序遍历需要访问所有节点，最差情况下需要访问 N+1 个 null ，总体复杂度为 O(2N + 1) = O(N) 。
空间复杂度 O(N)： 最差情况下，队列 queue 同时存储 (N + 1)/2 节点（或 N+1 个 null ），使用 O(N) ；列表 res 使用 O(N) 。
复杂度分析：
时间复杂度 O(N)： N 为二叉树的节点数，按层构建二叉树需要遍历整个节点，其长度最大为 2N+1 。
空间复杂度 O(N)： 最差情况下，队列 queue 同时存储 (N + 1)/2}个节点，因此使用 O(N)O(N) 额外空间。
如果这个时候还记得我们遍历二叉树的话，我们应该忘记不了 DFS。那么 DFS 我们用递归是否能够简化下代码呢？
序列化
递归的第一步都是特例的处理，因为这是递归的中止条件：如果根节点为空，返回”null“
序列化的结果为：根节点值 + "," + 左子节点值(进入递归) + "," + 右子节点值(进入递归)
递归就是不断将“根节点”值加到结果中的过程
反序列化
先将字符串转换成队列
接下来就进入了递归
i. 弹出左侧元素，即队列出队
ii. 如果元素为“null”，返回 null
iii. 否则，新建一个值为弹出元素的新节点
iv. 其左子节点为队列的下一个元素，进入递归；右子节点为队列的下下个元素，也进入递归
v. 递归就是不断将子树的根节点连接到父节点的过程
参考链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/jian-zhi-offer-37-xu-lie-hua-er-cha-shu-zgixr/
// Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null){ return "null"; } StringBuilder sb = new StringBuilder();
//中序遍历-利用递归思路将根-左子树-右子树进行处理 return sb.append(root.val).append(",").append(serialize(root.left)).append(",").append(serialize(root.right)).toString(); }
// Decodes your encoded data to tree. public TreeNode deserialize2(String data) { //构建队列数据 Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(","))); return dfs(queue); }
private TreeNode dfs(Queue<String> queue) { //遍历队列数据进行中序遍历 String val = queue.poll(); if("null".equals(val)){ return null; } TreeNode root = new TreeNode(Integer.parseInt(val)); root.left = dfs(queue); root.right = dfs(queue); return root; }
复制代码
复杂度分析
时间复杂度：O(n)
四、小结
其实虽然本题是 hard 题目，但是实际上本身来说，还是考查了面试者对于 DFS 和 BFS 的灵活应用。
评论