Serialize and Deserialize Binary Tree
序列化和反序列化一个二叉树. 需要注意两个特殊情况, 一个是node是null的情况, 一个是 node直接的分隔号.
|
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 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { private static final String spliter = ","; private static final String NN = "X"; // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); build(root, sb); return sb.toString(); } private void build(TreeNode root, StringBuilder sb) { if(root == null) sb.append(NN).append(spliter); else{ sb.append(root.val).append(spliter); build(root.left, sb); build(root.right, sb); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { Deque<String> nodes = new LinkedList<>(); nodes.addAll(Arrays.asList(data.split(spliter))); return buildTree(nodes); } private TreeNode buildTree(Deque<String> nodes) { String val = nodes.remove(); if(val.equals(NN)) return null; TreeNode node = new TreeNode(Integer.valueOf(val)); node.left = buildTree(nodes); node.right = buildTree(nodes); return node; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root)); |