题目描述：请实现两个函数，分别用来序列化和反序列化二叉树。
题目分析： 序列化二叉树其实就是一个广度优先遍历(BFS)，每一层从左到右遍历即可，此时可以选择使用一个队列，从头节点添加，遍历队列，判断左右节点，不为空则加入队列，此时我们可以使用一个StringBuilder来构建最终的字符串结果：
序列化代码如下：
1 public String serialize(TreeNode root) { 2 3 // 若头为空则返回一个空序列化结果 4 if (root == null) { 5 return "[]"; 6 } 7 8 9 // 定义一个队列同于遍历树 10 Queue<TreeNode> queue = new LinkedList<>(); 11 queue.add(root); 12 13 // StringBuilder构建最终字符串 14 StringBuilder string = new StringBuilder(); 15 16 // 字符串首为“[” 17 string.append("["); 18 19 TreeNode cur; 20 21 // 遍历队列 22 while(!queue.isEmpty()) { 23 24 // 出队 25 cur = queue.poll(); 26 27 // 出队为null则将null加入字符串 28 if (cur == null) { 29 string.append("null"); 30 string.append(","); 31 32 } else { 33 queue.add(cur.left); 34 queue.add(cur.right); 35 string.append(cur.val); 36 string.append(","); 37 } 38 } 39 40 // 将字符串末尾改为“]” 41 string.setCharAt(string.length()-1,']'); 42 43 44 return string.toString(); 45 46 47 }
反序列化其实就是将返回的字符串进行处理，将字符串中的字符串取出变为int类型数字或者null，主要的难点在于将字符串与节点建立联系与字符串的处理，这时同样采取队列的形式，将字符串处理之后，每个元素添加进队列，取出头节点，然后遍历队列中的元素，构建新的节点添加节点即可，如果为空则什么都不做即可（如果不为空寂左到右添加节点即可）
反序列化代码如下：
1 public TreeNode deserialize(String data) { 2 // 如果为空则返回null 3 if (data.equals("[]") || data == null) { 4 return null; 5 } 6 // 将字符串变为字符数组，去掉头尾”[“， “]” 7 String[] strings = data.substring(1, data.length()-1).split(","); 8 9 // 将头节点构建 10 TreeNode root = new TreeNode(Integer.parseInt(strings[0])); 11 12 // 使用队列 13 Queue<TreeNode> queue = new LinkedList<>(); 14 queue.add(root); 15 16 int index = 1; 17 while(!queue.isEmpty()) { 18 TreeNode cur = queue.poll(); 19 // 字符串不是null ，添加左节点 20 if (!strings[index].equals("null")) { 21 cur.left = new TreeNode(Integer.parseInt(strings[index])); 22 queue.add(cur.left); 23 24 } 25 26 // 字符串数组指针后移 27 index++; 28 29 // 字符串不是null ，添加右节点 30 if (!strings[index].equals("null")) { 31 cur.right = new TreeNode(Integer.parseInt(strings[index])); 32 queue.add(cur.right); 33 34 } 35 36 // 字符串数组指针后移 37 index++; 38 39 } 40 41 42 return root; 43 44 }
整体代码如下
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Codec { 11 12 13 14 // Encodes a tree to a single string. 15 public String serialize(TreeNode root) { 16 17 // 若头为空则返回一个空序列化结果 18 if (root == null) { 19 return "[]"; 20 } 21 22 23 // 定义一个队列同于遍历树 24 Queue<TreeNode> queue = new LinkedList<>(); 25 queue.add(root); 26 27 // StringBuilder构建最终字符串 28 StringBuilder string = new StringBuilder(); 29 30 // 字符串首为“[” 31 string.append("["); 32 33 TreeNode cur; 34 35 // 遍历队列 36 while(!queue.isEmpty()) { 37 38 // 出队 39 cur = queue.poll(); 40 41 // 出队为null则将null加入字符串 42 if (cur == null) { 43 string.append("null"); 44 string.append(","); 45 46 } else { 47 queue.add(cur.left); 48 queue.add(cur.right); 49 string.append(cur.val); 50 string.append(","); 51 } 52 } 53 54 // 将字符串末尾改为“]” 55 string.setCharAt(string.length()-1,']'); 56 57 58 return string.toString(); 59 60 61 } 62 63 // Decodes your encoded data to tree. 64 public TreeNode deserialize(String data) { 65 // 如果为空则返回null 66 if (data.equals("[]") || data == null) { 67 return null; 68 } 69 // 将字符串变为字符数组，去掉头尾”[“， “]” 70 String[] strings = data.substring(1, data.length()-1).split(","); 71 72 // 将头节点构建 73 TreeNode root = new TreeNode(Integer.parseInt(strings[0])); 74 75 // 使用队列 76 Queue<TreeNode> queue = new LinkedList<>(); 77 queue.add(root); 78 79 int index = 1; 80 while(!queue.isEmpty()) { 81 TreeNode cur = queue.poll(); 82 // 字符串不是null ，添加左节点 83 if (!strings[index].equals("null")) { 84 cur.left = new TreeNode(Integer.parseInt(strings[index])); 85 queue.add(cur.left); 86 87 } 88 89 // 字符串数组指针后移 90 index++; 91 92 // 字符串不是null ，添加右节点 93 if (!strings[index].equals("null")) { 94 cur.right = new TreeNode(Integer.parseInt(strings[index])); 95 queue.add(cur.right); 96 97 } 98 99 // 字符串数组指针后移 100 index++; 101 102 } 103 104 105 return root; 106 107 } 108 }