297. Serialize and Deserialize Binary Tree.md

297. Serialize and Deserialize Binary Tree

---

leetcode-cn Daily Challenge on June 16, 2020.

---

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

---

Solution

• mine

  • Java

    Runtime: 9 ms, faster than 76.65%, Memory Usage: 40.8 MB, less than 92.82% of Java online submissions

    // O(N)time O(N)space
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        LinkedList<TreeNode> record = new LinkedList<>();
        record.add(root);
        LinkedList<TreeNode> list = new LinkedList<>();
        while (record.size() > 0) {
            TreeNode node = record.removeFirst();
            if (node == null) {
                list.add(null);
                continue;
            }
            list.add(node);
            if (node.left == null) {
                record.add(null);
            } else {
                record.add(node.left);
            }
            if (node.right == null) {
                record.add(null);
            } else {
                record.add(node.right);
            }
        }
        while (list.getLast() == null) {
            list.removeLast();
        }
        StringBuilder sb = new StringBuilder();
        while (list.size() > 0) {
            TreeNode node = list.removeFirst();
            if (node == null) {
                sb.append("null").append(",");
            } else {
                sb.append(node.val).append(",");
            }
        }
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] arr = data.split(",");
        TreeNode res = new TreeNode(Integer.parseInt(arr[0]));
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(res);
        for (int i = 1; i < arr.length; i += 2) {
            TreeNode node = list.removeFirst();
            if ("null".equals(arr[i])) {
                node.left = null;
            } else {
                TreeNode left = new TreeNode(Integer.parseInt(arr[i]));
                list.add(left);
                node.left = left;
            }
            if (i + 1 >= arr.length) {
                break;
            }
            if ("null".equals(arr[i + 1])) {
                node.right = null;
            } else {
                TreeNode right = new TreeNode(Integer.parseInt(arr[i + 1]));
                list.add(right);
                node.right = right;
            }
        }
        return res;
    }
    

---

• the most votes

  Runtime: 7 ms, faster than 93.40%, Memory Usage: 41 MB, less than 86.17% of Java online submissions

  // O(N)time O(N)space
  
  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();
      buildString(root, sb);
      return sb.toString();
  }
  
  private void buildString(TreeNode node, StringBuilder sb) {
      if (node == null) {
          sb.append(NN).append(spliter);
      } else {
          sb.append(node.val).append(spliter);
          buildString(node.left, sb);
          buildString(node.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;
      else {
          TreeNode node = new TreeNode(Integer.valueOf(val));
          node.left = buildTree(nodes);
          node.right = buildTree(nodes);
          return node;
      }
  }
  

---