Skip to content

449. Serialize and Deserialize BST 👍

  • Time:
    • Constructor: $O(1)$
    • serialize(root: TreeNode): $O(n)$
    • deserialize(data: str): $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    if (root == nullptr)
      return "";
    string s;
    serialize(root, s);
    return s;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    if (data.empty())
      return nullptr;

    istringstream iss(data);
    queue<int> q;

    for (string s; iss >> s;)
      q.push(stoi(s));

    return deserialize(INT_MIN, INT_MAX, q);
  }

 private:
  void serialize(TreeNode* root, string& s) {
    if (root == nullptr)
      return;
    s += to_string(root->val) + " ";
    serialize(root->left, s);
    serialize(root->right, s);
  }

  TreeNode* deserialize(int mn, int mx, queue<int>& q) {
    if (q.empty())
      return nullptr;

    const int val = q.front();
    if (val < mn || val > mx)
      return nullptr;

    q.pop();
    TreeNode* root = new TreeNode(val);
    root->left = deserialize(mn, val, q);
    root->right = deserialize(val, mx, q);
    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Codec {
  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    if (root == null)
      return "";
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    if (data.isEmpty())
      return null;

    final String[] vals = data.split(" ");
    Queue<Integer> q = new ArrayDeque<>();

    for (final String val : vals)
      q.offer(Integer.parseInt(val));

    return deserialize(Integer.MIN_VALUE, Integer.MAX_VALUE, q);
  }

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

  private TreeNode deserialize(int mn, int mx, Queue<Integer> q) {
    if (q.isEmpty())
      return null;

    final int val = q.peek();
    if (val < mn || val > mx)
      return null;

    q.poll();
    TreeNode root = new TreeNode(val);
    root.left = deserialize(mn, val, q);
    root.right = deserialize(val, mx, q);
    return root;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Codec:
  def serialize(self, root: TreeNode | None) -> str:
    """Encodes a tree to a single string."""
    if not root:
      return ''
    chars = []
    self._serialize(root, chars)
    return ''.join(chars)

  def deserialize(self, data: str) -> TreeNode | None:
    """Decodes your encoded data to tree."""
    if not data:
      return None
    q = collections.deque(int(val) for val in data.split())
    return self._deserialize(-math.inf, math.inf, q)

  def _serialize(self, root: TreeNode | None, chars: list[str]) -> None:
    if not root:
      return
    chars.append(str(root.val))
    chars.append(' ')
    self._serialize(root.left, chars)
    self._serialize(root.right, chars)

  def _deserialize(
      self,
      mn: int,
      mx: int,
      q: collections.deque[int]
  ) -> TreeNode | None:
    if not q:
      return None

    val = q[0]
    if val < mn or val > mx:
      return None

    q.popleft()
    return TreeNode(val,
                    self._deserialize(mn, val, q),
                    self._deserialize(val, mx, q))