二叉树的序列化
先说结论：
如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文所说，分两种情况：
2.1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
2.2. 如果你给出前序和后序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。
如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
3.1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
3.2. 如果你给出的是中序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。
前序遍历的序列化与反序列化
297. 二叉树的序列化与反序列化[hard]
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
二叉树结构是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化不过就是把结构化的数据「打平」，本质就是在考察二叉树的遍历方式。
// 代表分隔符的字符 String SEP = ","; // 代表 null 空指针的字符 String NULL = "#"; /* 主函数，将二叉树序列化为字符串 */ String serialize(TreeNode root) { // 用于拼接字符串 StringBuilder sb = new StringBuilder(); serialize(root, sb); return sb.toString(); } /* 辅助函数，将二叉树存入 StringBuilder */ void serialize(TreeNode root, StringBuilder sb) { if (root == null) { sb.append(NULL).append(SEP); return; } /****** 前序位置 ******/ sb.append(root.val).append(SEP); /***********************/ serialize(root.left, sb); serialize(root.right, sb); }
反序列化过程也是一样，先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树即可
完整代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // 代表分隔符的字符 String SEP = ","; // 代表 null 空指针的字符 String NULL = "#"; // Encodes a tree to a single string. public String serialize(TreeNode root) { // 用于拼接字符串 StringBuilder sb = new StringBuilder(); serializeHelp(root, sb); return sb.toString(); } /* 辅助函数，将二叉树存入 StringBuilder */ private void serializeHelp(TreeNode root, StringBuilder sb) { if (root == null) { sb.append(NULL).append(SEP); return; } /****** 前序位置 ******/ sb.append(root.val).append(SEP); /***********************/ serializeHelp(root.left, sb); serializeHelp(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.length() == 0) return null; String[] nodes = data.split(","); return deserializeHelp(nodes); } int nodesStart = 0; private TreeNode deserializeHelp(String[] nodes){ if(nodesStart > nodes.length) return null; if(nodes[nodesStart].equals("#")){ nodesStart++; return null; } int rootVal = new Integer(nodes[nodesStart]); nodesStart++; TreeNode root = new TreeNode(rootVal); root.left = deserializeHelp(nodes); root.right = deserializeHelp(nodes); return root; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // TreeNode ans = deser.deserialize(ser.serialize(root));
