题目描述
设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。
样例:二叉树{3,9,20,#,#,15,7}
数结构如下:
思路
序列化:其实就是如何遍历二叉树。
因为不知道二叉树有多少个节点,所以考虑ArrayList。
因为考虑到要反序列化,所以对空的子节点,其val用“#”标识。
因为是动态的添加字符到字符串,考虑StringBuilder。
- 初始化List和StringBuilder
先取root的val,append到StringBuilder。然后把root add到List。
- 遍历list,将当前节点的左右子节点add到List,将子节点的val append到StringBuilder
- 如果子节点为null,将”#”append到StringBuilder
反序列化:其实就是根据字符串恢复二叉树。
首先将字符串处理成String[]{val1,val2,val3 …}的形式
用val1创建root
因为String[]保存的是完全二叉树的val(空节点为”#”),考虑遍历String[]恢复二叉树
因为不知道二叉树包含多少个节点,考虑用ArrayList保存节点
用Index指向当前恢复的节点在List中的下标
- 遍历String[]
- 读完一组val,创建左右子节点并加入List,当前节点的left、right指向子节点,index++
- 如果读到“#”,不创建子节点,但读完一组后,index++(因为要准确恢复二叉树)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| public String serialize(TreeNode root) { if(root == null) return null; StringBuilder sBuilder = new StringBuilder("{"); sBuilder.append(root.val); ArrayList<TreeNode> aList = new ArrayList<TreeNode>(); aList.add(root); for(int i = 0; i < aList.size(); i++) { if(aList.get(i) == null) continue; aList.add(aList.get(i).left); aList.add(aList.get(i).right); if(aList.get(i).left != null) { sBuilder.append("," + aList.get(i).left.val); }else { sBuilder.append(",#"); } if(aList.get(i).right != null) { sBuilder.append("," + aList.get(i).right.val); }else { sBuilder.append(",#"); } } sBuilder.append("}"); return sBuilder.toString(); } public TreeNode deserialize(String data) { if(data == null) return null; String[] strings = data.substring(1, data.length()-1).split(","); TreeNode root = new TreeNode(Integer.parseInt(strings[0])); ArrayList<TreeNode> aList = new ArrayList<TreeNode>(); aList.add(root); int index = 0; boolean isLeft = true; for(int i = 1; i < strings.length; i++) { if(!strings[i].equals("#")) { TreeNode node = new TreeNode(Integer.parseInt(strings[i])); if(isLeft) { aList.get(index).left = node; aList.add(node); }else { aList.get(index).right = node; aList.add(node); } } isLeft = !isLeft; if(isLeft) index++; } return root; }
|
考差点
- 二叉树的遍历(用ArrayList保存当前读取的节点和子节点
将要读取的节点
)
- 二叉树的还原(用ArrayList保存当前恢复的节点和其指向的子节点
将要恢复的节点
)