449. Serialize and Deserialize BST

• 449. Serialize and Deserialize BST
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

这题目与二叉树那道题的主要区别是要求string尽量compact

解法比较直接，其实直接使用preorder就可以了

Pitfall

Solution

  private static final String SEP = ",";

  public String serialize(TreeNode root) {
    final StringBuilder sb = new StringBuilder();
    preOrder(root, sb);
    return sb.length() == 0 ? "" : sb.substring(1);
  }

  private void preOrder(TreeNode root, StringBuilder sb) {
    if (root == null) {
      return;
    }
    sb.append(SEP).append(root.val);
    preOrder(root.left, sb);
    preOrder(root.right, sb);
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    if (data.length() == 0) {
      return null;
    }
    final Queue<Integer> queue = Arrays.stream(data.split(SEP)).map(Integer::parseInt).collect(Collectors.toCollection(ArrayDeque::new));
    return deserialize(queue, Long.MIN_VALUE, Long.MAX_VALUE);
  }

  private static TreeNode deserialize(final Queue<Integer> queue, final long min, final long max) {
    if (!queue.isEmpty() && min < queue.peek() && queue.peek() < max) {
      final TreeNode root = new TreeNode(queue.remove());
      root.left = deserialize(queue, min, root.val);
      root.right = deserialize(queue, root.val, max);
      return root;
    }
    return null;
  }