449.Serialize-and-Deserialize-BST

449. Serialize and Deserialize BST

题目地址

https://leetcode.com/problems/serialize-and-deserialize-bst/

题目描述

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

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

代码

Approach #3 Preorder, 正常顺序

Preorder, 空节点用null=> 1.先访问字符，2. Left, 3. Right,

解析时从0头部开始 => 1.先访问，2. left, 3.right

/**
 * 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 1: Postorder traversal 反向顺序

Postorder, 从前往后拼接String => 1.left, 2. Right, 3. Val

解析的时候，从后last往前读取，逆向postorder => 1.访问，2.right, 3. Left

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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;
  }

  public String serialize(TreeNode root) {
    StringBuilder sb = postorder(root, new StringBuilder());
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
  }

  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 low, Integer upper, ArrayDeque<Integer> nums){
    if (nums.isEmpty())    return null;
    int val = nums.getLast();
    if (val < lower || val > uper)    return null;

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

Approach #2 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 bytes string to integer
  public int stringToInt(String bytesStr) {
    int result = 0;
    for(char b : bytesStr.toCharArray()) {
      result = (result << 8) + (int)b;
    }
    return result;
  }

  // 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;    // as delimiter
        // root -> right -> left
    nums.removeLast();
    TreeNode root = new TreeNode(val);
    root.right = helper(val, upper, nums);
    root.left = helper(lower, val, nums);
    return root;
  }

}