一、题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
二、思路讲解
思路上倒没什么好说的，二叉树的广度优先遍历，具体的讲解可以参考我之前的博客，略有不同。
二叉树的层序遍历 Java广度优先搜索_m0_49499183的博客-CSDN博客
之所以在力扣中被定义为困难难度，可能是因为他确实很重要吧。
三、Java代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root==null){ return "[]"; } StringBuffer res =new StringBuffer("["); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode temp = queue.poll(); if(temp != null){ res.append(temp.val + ","); queue.add(temp.left); queue.add(temp.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])); int index = 1; //用于遍历字符串数组vals Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode temp = queue.poll(); if(!vals[index].equals("null")){ temp.left = new TreeNode(Integer.parseInt(vals[index])); queue.add(temp.left); } index++; if(!vals[index].equals("null")){ temp.right = new TreeNode(Integer.parseInt(vals[index])); queue.add(temp.right); } index++; } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
四、时空复杂度分析
就是BFS的时空复杂度了
时间复杂度： O(N)
空间复杂度： O(N)
