序列化二叉树

2019-11-08 03:01:18

字体：大中小

来源：转载

供稿：网友

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

算法解析：我们序列化后的字符串以根节点为开始，并且希望可以完美的描述二叉树，所以我们将null结点作为”$”传入，最后利用前序遍历形成字符串，反序列就是利用前序遍历的方式生成该树，注意的是，这里我们要传入参数的时候，应该利用数组是引用类型这个特性。

代码如下：

String Serialize(TreeNode root) { StringBuilder builder = new StringBuilder(); if (root == null){ builder.append("$,"); }else{ builder.append(root.val); builder.append(","); builder.append(Serialize(root.left)); builder.append(Serialize(root.right)); } return builder.toString(); } TreeNode Deserialize(String str) { String [] datas = str.split(","); int[] pos = new int[1]; return Deserialize(datas, pos); } TreeNode Deserialize(String [] datas, int[] pos) { TreeNode root; if (pos[0] == datas.length){ return null; } String data = datas[pos[0]]; if (data.compareTo("$") == 0){ root = null; }else { root = new TreeNode(Integer.valueOf(data)); pos[0] ++; root.left = Deserialize(datas, pos); pos[0] ++; root.right = Deserialize(datas, pos); } return root; }

上一篇：字符串的反转

下一篇：LeetCode:maximum-depth-of-binary-tree