本文共 1336 字,大约阅读时间需要 4 分钟。
题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。
分析
如果二叉树的序列化是从根节点开始,那么对应的而反序列化也是从根节点开始的。因此可以使用二叉树的前序遍历来序列化二叉树,当前序遍历碰到null值是,使用“#”表示,每一个节点的数值之间用“,”隔开。
牛客AC:
/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public int index = -1; // 节点在序列中的索引 /** * 序列化 * 前序遍历,将二叉树节点的值转为字符序列,null转为“#” * * @param root * @return */ String Serialize(TreeNode root) { StringBuffer s = new StringBuffer(); if (root == null) { s.append("#,"); return s.toString(); } s.append(root.val + ","); s.append(Serialize(root.left)); s.append(Serialize(root.right)); return s.toString(); } /** * 反序列化 * * @param str * @return */ TreeNode Deserialize(String str) { index++; int length = str.length(); if (index >= length) { return null; } String[] nodeSeq = str.split(","); TreeNode pNode = null; if (!nodeSeq[index].equals("#")) { pNode = new TreeNode(Integer.valueOf(nodeSeq[index])); pNode.left = Deserialize(str); pNode.right = Deserialize(str); } return pNode; }}
参考
1. 何海涛,剑指offer名企面试官精讲典型编程题(纪念版),电子工业出版社转载地址:http://xkxgi.baihongyu.com/