297. Serialize and Deserialize Binary Tree

Approach 1: BFS

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    if (root == nullptr)
      return "";

    string s;
    queue<TreeNode*> q{{root}};

    while (!q.empty()) {
      TreeNode* node = q.front();
      q.pop();
      if (node != nullptr) {
        s += to_string(node->val) + " ";
        q.push(node->left);
        q.push(node->right);
      } else {
        s += "n ";
      }
    }

    return s;
  }

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

    istringstream iss(data);
    string word;
    iss >> word;
    TreeNode* root = new TreeNode(stoi(word));
    queue<TreeNode*> q{{root}};

    while (iss >> word) {
      TreeNode* node = q.front();
      q.pop();
      if (word != "n") {
        node->left = new TreeNode(stoi(word));
        q.push(node->left);
      }
      iss >> word;
      if (word != "n") {
        node->right = new TreeNode(stoi(word));
        q.push(node->right);
      }
    }

    return root;
  }
};

public class Codec {
  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    if (root == null)
      return "";

    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));

    while (!q.isEmpty()) {
      TreeNode node = q.poll();
      if (node == null) {
        sb.append("n ");
      } else {
        sb.append(node.val).append(" ");
        q.offer(node.left);
        q.offer(node.right);
      }
    }

    return sb.toString();
  }

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

    final String[] vals = data.split(" ");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));

    for (int i = 1; i < vals.length; i += 2) {
      TreeNode node = q.poll();
      if (!vals[i].equals("n")) {
        node.left = new TreeNode(Integer.parseInt(vals[i]));
        q.offer(node.left);
      }
      if (!vals[i + 1].equals("n")) {
        node.right = new TreeNode(Integer.parseInt(vals[i + 1]));
        q.offer(node.right);
      }
    }

    return root;
  }
}

class Codec:
  def serialize(self, root: 'TreeNode') -> str:
    """Encodes a tree to a single string."""
    if not root:
      return ''

    s = ''
    q = collections.deque([root])

    while q:
      node = q.popleft()
      if node:
        s += str(node.val) + ' '
        q.append(node.left)
        q.append(node.right)
      else:
        s += 'n '

    return s

  def deserialize(self, data: str) -> 'TreeNode':
    """Decodes your encoded data to tree."""
    if not data:
      return None

    vals = data.split()
    root = TreeNode(vals[0])
    q = collections.deque([root])

    for i in range(1, len(vals), 2):
      node = q.popleft()
      if vals[i] != 'n':
        node.left = TreeNode(vals[i])
        q.append(node.left)
      if vals[i + 1] != 'n':
        node.right = TreeNode(vals[i + 1])
        q.append(node.right)

    return root

Approach 2: DFS

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    string s;
    preorder(root, s);
    return s;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    istringstream iss(data);
    queue<string> q;

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

    return preorder(q);
  }

 private:
  void preorder(TreeNode* root, string& s) {
    if (root == nullptr) {
      s += "n ";
      return;
    }

    s += to_string(root->val) + " ";
    preorder(root->left, s);
    preorder(root->right, s);
  }

  TreeNode* preorder(queue<string>& q) {
    const string s = q.front();
    q.pop();
    if (s == "n")
      return nullptr;

    TreeNode* root = new TreeNode(stoi(s));
    root->left = preorder(q);
    root->right = preorder(q);
    return root;
  }
};

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

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    final String[] vals = data.split(" ");
    Queue<String> q = new ArrayDeque<>(Arrays.asList(vals));
    return preorder(q);
  }

  private void preorder(TreeNode root, StringBuilder sb) {
    if (root == null) {
      sb.append("n ");
      return;
    }

    sb.append(root.val).append(" ");
    preorder(root.left, sb);
    preorder(root.right, sb);
  }

  private TreeNode preorder(Queue<String> q) {
    final String s = q.poll();
    if (s.equals("n"))
      return null;

    TreeNode root = new TreeNode(Integer.parseInt(s));
    root.left = preorder(q);
    root.right = preorder(q);
    return root;
  }
}

class Codec:
  def serialize(self, root: 'TreeNode') -> str:
    """Encodes a tree to a single string."""
    s = []

    def preorder(root: 'TreeNode') -> None:
      if not root:
        s.append('n')
        return

      s.append(str(root.val))
      preorder(root.left)
      preorder(root.right)

    preorder(root)
    return ' '.join(s)

  def deserialize(self, data: str) -> 'TreeNode':
    """Decodes your encoded data to tree."""
    q = collections.deque(data.split())

    def preorder() -> 'TreeNode':
      s = q.popleft()
      if s == 'n':
        return None

      root = TreeNode(s)
      root.left = preorder()
      root.right = preorder()
      return root

    return preorder()