297.Serialize-and-Deserialize-Binary-Tree

297. Serialize and Deserialize Binary Tree

题目地址

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

题目描述

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.

代码

Approach 1: Depth First Search (DFS)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
  // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return preorder(root, "");
    }

  public String preorder(TreeNode root, String str) {
    if (root == null) {
      str += "null,";
    } else {
      str += str.valueOf(root.val) + ",";
      str = preorder(root.left, str);
      str = preorder(root.right, str);
    }
    return str;
  }

  // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));

        return rdeserialize(data_list);
    }

  public TreeNode rdeserialize(List<String> l) {
    if (l.get(0).equals("null")) {
      l.remove(0);
      return null;
    }

    TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
    l.remove(0);
    root.left = rdeserialize(l);
    root.right = rdeserialize(l);

    return root;
  }

}

Approach #2 Iterative Preorder DFS

class Codec {
    // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            Deque<TreeNode> stack = new LinkedList<>();
            while (root != null || !stack.isEmpty()) {
                if (root != null) {
                    sb.append(String.valueOf(root.val) + ",");
                    stack.push(root); // 压入已访问的root
                    root = root.left;
                } else {
                    sb.append("null,");
                    root = stack.pop();
                    root = root.right;
                }
            }
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.length() == 0) return null;
            String[] data_array = data.split(",");
            Queue<String> data_list = new LinkedList<String>(Arrays.asList(data_array));

            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.valueOf(data_list.poll()));
            TreeNode x = root;
            stack.push(x);

            while (!data_list.isEmpty()) {
                // left
                while (!data_list.peek().equals("null")) {
                    x.left = new TreeNode(Integer.valueOf(data_list.poll()));
                    x = x.left;
                    stack.push(x); // 压入已访问的 x.left
                }

                // equal null
                while (!data_list.isEmpty() && data_list.peek().equals("null")) {
                    x = stack.pop();
                    data_list.poll();
                }

                // right
                if (!data_list.isEmpty()) {
                    x.right = new TreeNode(Integer.valueOf(data_list.poll()));
                    x = x.right;
                    stack.push(x);
                }

            }
            return root;
        }
}

Approach #3 BFS Preorder

class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        q.offer(root);
        sb.append(String.valueOf(root.val) + ",");
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null) {
                sb.append("null,");
            } else {
                q.offer(node.left);
                sb.append(String.valueOf(node.left.val) + ",");
            }
            if (node.right == null) {
                sb.append("null,");
            } else {
                q.offer(node.right);
                sb.append(String.valueOf(node.right.val) + ",");
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String str) {
        if (str.length() == 0) return null;
        String[] data_array = str.split(",");
        Queue<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.valueOf(data_list.poll()));
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();

            // left
            if (data_list.peek().equals("null")) {
                node.left = null;
            } else {
                node.left = new TreeNode(Integer.valueOf(data_list.peek()));
                q.offer(node.left);
            }
            data_list.poll();

            // right
            if (data_list.peek().equals("null")) {
                node.right = null;
            } else {
                node.right = new TreeNode(Integer.valueOf(data_list.peek()));
                q.offer(node.right);
            }
            data_list.poll();
        }

        return root;
    }
}

Approach #3 Postorder traversal to optimise space for the tree structure

public class Codec {
  public StringBuilder postorder(TreeNode root, StringBuilder sb) {
    if (root == null) return sb;
    postorder(root.left, sb);
    postorder(root.right, sb);
    sb.append(root.val);
    sb.append(' ');
    return sb;
  }

  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    StringBuilder sb = postorder(root, new StringBuilder());
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
    for (String s : data.split("\\s+"))
      nums.add(Integer.valueOf(s));
    return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
  }

   public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
    if (nums.isEmpty()) return null;
    int val = nums.getLast();
    if (val < lower || val > upper) return null;

    nums.removeLast();
    TreeNode root = new TreeNode(val);
    root.right = helper(val, upper, nums);
    root.left = helper(lower, val, nums);
    return root;
  }

}

Approach #3 Get rid of delimiters

public class Codec {
  // Encodes a tree to a list.
  public void postorder(TreeNode root, StringBuilder sb) {
    if (root == null) return;
    postorder(root.left, sb);
    postorder(root.right, sb);
    sb.append(intToString(root.val));
  }

  // Encodes integer to bytes string
  public String intToString(int x) {
    char[] bytes = new char[4];
    for(int i = 3; i > -1; --i) {
      bytes[3 - i] = (char) (x >> (i * 8) & 0xff);
    }
    return new String(bytes);
  }

  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    postorder(root, sb);
    return sb.toString();
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
    int n = data.length();
    for(int i = 0; i < (int)(n / 4); ++i) {
      nums.add(stringToInt(data.substring(4 * i, 4 * i + 4)));
    }

    return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
  }

    // Decodes list to tree.
  public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
    if (nums.isEmpty()) return null;
    int val = nums.getLast();
    if (val < lower || val > upper) return null;

    nums.removeLast();
    TreeNode root = new TreeNode(val);
    root.right = helper(val, upper, nums);
    root.left = helper(lower, val, nums);
    return root;
  }

  // Decodes bytes string to integer
  public int stringToInt(String bytesStr) {
    int result = 0;
    for(char b : bytesStr.toCharArray()) {
      result = (result << 8) + (int)b;
    }
    return result;
  }
}