SerializeDeserializeBinaryTree

class Node {
  int val;
  Node left;
  Node right;
}

public String serialize(Node root) {
  StringBuilder sb = new StringBuilder();
  serialize(root, sb);
  return sb.toString();
}

private String serialize(Node node, StringBuilder sb) {
  if (node == null) {
    sb.append("# ");
  } else {
    sb.append(String.format("%d ", node.val));
    serialize(node.left);
    serialize(node.right);
  }
}

public Node deserialize(String str) {
  Queue <String> q = new Queue<String>();
  for (String token: str.split(" ")) {
    q.add(token);
  }
  return deserialize(q);
}

private Node deserialize(Queue <String> q) {
  if (!q.empty()) {
    String token = q.pop();
    if (!token.equals("#")) {
      Node node = new Node(Integer.parseInt(token));
      node.left = deserialize(q);
      node.right = deserialize(q);
    }
  }
  return null;
}