劍指Offer_61_序列化二叉樹

題目描述

請實現兩個函數，分別用來序列化和反序列化二叉樹

解題思路

使用前序遍歷，將遇到的結點添加到字符串中，遇到null則將一個#添加要序列化字符串中。反序列化時，每次讀取根結點，然后讀取其左結點，遇到#（null）時，返回上層。

實現

/*樹結點定義*/
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
/*實現*/
public class Solution {String Serialize(TreeNode root) {StringBuilder sb = new StringBuilder();serialize(root, sb);return sb.toString();}private void serialize(TreeNode root, StringBuilder sb) {if (root == null) {sb.append("#,");return;}sb.append(root.val + ",");serialize(root.left, sb);serialize(root.right, sb);}private class Result{TreeNode node;int pos;Result(TreeNode node, int pos){this.node = node;this.pos = pos;}}TreeNode Deserialize(String str) {if (str == null || str.length() <= 0) return null;String[] strs = str.split(",");Result re = deserialize(strs, 0);return re.node;}private Result deserialize(String[] str, int i) {TreeNode root = null;if (i < str.length - 1){if ("#".equals(str[i])) return new Result(null, i+1);root = new TreeNode(Integer.parseInt(str[i]));Result l = deserialize(str, i + 1);root.left = l.node;Result r = deserialize(str, l.pos);root.right = r.node;return new Result(root, r.pos);}return new Result(root, i+1);}
}