Binary Tree Serialization

Question

  1. Design an algorithm and write code to serialize and deserialize a binary tree.
  2. Writing the tree to a file is called 'serialization'
  3. and reading back from the file to reconstruct
  4. the exact same binary tree is 'deserialization'.
  5. There is no limit of how you deserialize or serialize a binary tree,
  6. you only need to make sure you can serialize a binary tree to a string
  7. and deserialize this string to the original structure.
  8. Have you met this question in a real interview? Yes
  9. Example
  10. An example of testdata: Binary tree {3,9,20,#,#,15,7},
  11. denote the following structure:
  12.   3
  13.  / \
  14. 9  20
  15.   /  \
  16.  15   7
  17. Our data serialization use bfs traversal.
  18. This is just for when you got wrong answer and want to debug the input.
  20. You can use other method to do serializaiton and deserialization.

题解

根据之前由前序，中序，后序遍历恢复二叉树的经验，确定根节点的位置十分重要（但是这里可能有重复元素，故和之前的题目不太一样）。能直接确定根节点的有前序遍历和广度优先搜索，其中较为简洁的为前序遍历。序列化较为简单，但是反序列化的实现不太容易。需要借助字符串解析工具。

Python

  1. """
  2. Definition of TreeNode:
  3. class TreeNode:
  4.     def __init__(self, val):
  5.         self.val = val
  6.         self.left, self.right = None, None
  7. """
  8. """
  9. Definition of TreeNode:
  10. class TreeNode:
  11.     def __init__(self, val):
  12.         self.val = val
  13.         self.left, self.right = None, None
  14. """
  15. class Solution0:
  16.     '''
  17.     @param root: An object of TreeNode, denote the root of the binary tree.
  18.     This method will be invoked first, you should design your own algorithm
  19.     to serialize a binary tree which denote by a root node to a string which
  20.     can be easily deserialized by your own "deserialize" method later.
  21.     '''
  22.     def serialize(self, root):
  23.         if not root:
  24.             return ''
  26.         def post_order(root):
  27.             if root:
  28.                 post_order(root.left)
  29.                 post_order(root.right)
  30.                 ret[0] += str(root.val) + ','
  31.             else:
  32.                 ret[0] += '#,'
  34.         ret = ['']
  35.         post_order(root)
  37.         return ret[0][:-1]  # remove last ,
  39.     '''
  40.     @param data: A string serialized by your serialize method.
  41.     This method will be invoked second, the argument data is what exactly
  42.     you serialized at method "serialize", that means the data is not given by
  43.     system, it's given by your own serialize method. So the format of data is
  44.     designed by yourself, and deserialize it here as you serialize it in
  45.     "serialize" method.
  46.     '''
  47.     def deserialize(self, data):
  48.         if not data:
  49.             return
  51.         nodes = data.split(',')
  52.         def post_order(nodes):
  53.             if nodes[-1] == '#':
  54.                 nodes.pop()
  55.                 return None
  56.             root = TreeNode(int(nodes.pop()))
  57.             root.right = post_order(nodes)
  58.             root.left = post_order(nodes)
  59.             return root
  60.         return post_order(nodes)
  62. class Solution1:
  63.     '''
  64.     @param root: An object of TreeNode, denote the root of the binary tree.
  65.     This method will be invoked first, you should design your own algorithm
  66.     to serialize a binary tree which denote by a root node to a string which
  67.     can be easily deserialized by your own "deserialize" method later.
  68.     '''
  69.     def serialize(self, root):
  70.         if not root:
  71.             return ''
  73.         def pre_order(root):
  74.             if root:
  75.                 ret[0] += str(root.val) + ','
  76.                 pre_order(root.left)
  77.                 pre_order(root.right)
  78.             else:
  79.                 ret[0] += '#,'
  81.         ret = ['']
  82.         pre_order(root)
  84.         return ret[0][:-1]  # remove last ,
  86.     '''
  87.     @param data: A string serialized by your serialize method.
  88.     This method will be invoked second, the argument data is what exactly
  89.     you serialized at method "serialize", that means the data is not given by
  90.     system, it's given by your own serialize method. So the format of data is
  91.     designed by yourself, and deserialize it here as you serialize it in
  92.     "serialize" method.
  93.     '''
  94.     def deserialize(self, data):
  95.         if not data:
  96.             return
  98.         nodes = data.split(',')
  99.         self.i = 0
  100.         def pre_order(nodes):
  101.             if nodes[self.i] == '#':
  102.                 return None
  103.             root = TreeNode(int(nodes[self.i]))
  104.             self.i += 1
  105.             root.left = pre_order(nodes)
  106.             self.i += 1
  107.             root.right = pre_order(nodes)
  108.             return root
  109.         return pre_order(nodes)
  112. import collections
  113. class Solution2:
  115.     '''
  116.     @param root: An object of TreeNode, denote the root of the binary tree.
  117.     This method will be invoked first, you should design your own algorithm
  118.     to serialize a binary tree which denote by a root node to a string which
  119.     can be easily deserialized by your own "deserialize" method later.
  120.     '''
  121.     def serialize(self, root):
  122.         if not root:
  123.             return
  125.         ret = []
  126.         queue = collections.deque()
  127.         queue.append(root)
  128.         while queue:
  129.             node = queue.popleft()
  130.             if node:
  131.                 queue.append(node.left)
  132.                 queue.append(node.right)
  133.                 ret.append(str(node.val))
  134.             else:
  135.                 ret.append('#')
  136.         return ','.join(ret)
  138.     '''
  139.     @param data: A string serialized by your serialize method.
  140.     This method will be invoked second, the argument data is what exactly
  141.     you serialized at method "serialize", that means the data is not given by
  142.     system, it's given by your own serialize method. So the format of data is
  143.     designed by yourself, and deserialize it here as you serialize it in
  144.     "serialize" method.
  145.     '''
  146.     def deserialize(self, data):
  147.         if not data:
  148.             return
  149.         nodes = data.split(',')
  150.         root = TreeNode(int(nodes[0]))
  151.         i = 1
  152.         queue = collections.deque()
  153.         queue.append(root)
  154.         while queue:
  155.             node = queue.popleft()
  156.             if nodes[i] == '#':
  157.                 node.left = None
  158.             else:
  159.                 t = TreeNode(int(nodes[i]))
  160.                 node.left = t
  161.                 queue.append(t)
  162.             i += 1
  163.             if nodes[i] == '#':
  164.                 node.right = None
  165.             else:
  166.                 t = TreeNode(int(nodes[i]))
  167.                 node.right = t
  168.                 queue.append(t)
  169.             i += 1
  170.         return root

源码分析

第零种解法是后序遍历（推荐）， 在serialize的时候， 需要先左->右->中。 在deserialize的时候，因为是从最后一个值开始pop， 构成tree的时候， 就应该先中->右->左。

第一种解法是前序遍历， 其中巧妙的利用了python的closure， 在serialize中， 利用了list mutable 的特性， 修改了ret中的值。 deserialize中， 利用了self.i来储存instance variable。

第二种解法是广度遍历。 在deserialize的时候， 保持一个index i，记录用过的node。

Java

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  12. class Solution {
  13.     /**
  14.      * This method will be invoked first, you should design your own algorithm
  15.      * to serialize a binary tree which denote by a root node to a string which
  16.      * can be easily deserialized by your own "deserialize" method later.
  17.      */
  18.     public String serialize(TreeNode root) {
  19.         StringBuilder sb = new StringBuilder();
  20.         if (root == null) return sb.toString();
  22.         seriaHelper(root, sb);
  24.         return sb.substring(0, sb.length() - 1);
  25.     }
  27.     private void seriaHelper(TreeNode root, StringBuilder sb) {
  28.         if (root == null) {
  29.             sb.append("#,");
  30.         } else {
  31.             sb.append(root.val).append(",");
  32.             seriaHelper(root.left, sb);
  33.             seriaHelper(root.right, sb);
  34.         }
  35.     }
  37.     /**
  38.      * This method will be invoked second, the argument data is what exactly
  39.      * you serialized at method "serialize", that means the data is not given by
  40.      * system, it's given by your own serialize method. So the format of data is
  41.      * designed by yourself, and deserialize it here as you serialize it in
  42.      * "serialize" method.
  43.      */
  44.     public TreeNode deserialize(String data) {
  45.         if (data == null || data.length() == 0) return null;
  47.         StringTokenizer st = new StringTokenizer(data, ",");
  48.         return deseriaHelper(st);
  49.     }
  51.     private TreeNode deseriaHelper(StringTokenizer st) {
  52.         if (!st.hasMoreTokens()) return null;
  54.         String val = st.nextToken();
  55.         if (val.equals("#")) {
  56.             return null;
  57.         }
  59.         TreeNode root = new TreeNode(Integer.parseInt(val));
  60.         root.left = deseriaHelper(st);
  61.         root.right = deseriaHelper(st);
  63.         return root;
  64.     }
  65. }

源码分析

由二叉树序列化的过程不难，难就难在根据字符串进行反序列化，这里引入了 Java 中的 StringTokenizer 字符串分割工具，非常方便，使得递归得以顺利实现。其中deseriaHelper的实现较为巧妙。

复杂度分析

略

Reference