LeetCode Solutions

			

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

    string s;
    queue<Node*> q{{root}};
    s += to_string(root->val) + " ";

    while (!q.empty())
      for (int sz = q.size(); sz > 0; --sz) {
        Node* node = q.front();
        q.pop();
        if (node->children.empty()) {
          s += "n";
        } else {
          for (Node* child : node->children) {
            q.push(child);
            s += to_string(child->val) + "#";
          }
        }
        s += " ";
      }

    return s;
  }

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

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

    while (iss >> word) {
      Node* parent = q.front();
      q.pop();
      vector<string> kids = getKids(word);
      vector<Node*> children;
      for (const string& kid : kids) {
        if (kid == "n")
          continue;
        Node* child = new Node(stoi(kid));
        children.push_back(child);
        q.push(child);
      }
      parent->children = children;
    }

    return root;
  }

 private:
  vector<string> getKids(const string& word) {
    vector<string> kids;
    for (int i = 0, j = 0; j < word.length(); ++j)
      if (word[j] == '#') {
        kids.push_back(word.substr(i, j - i));
        i = j + 1;
      }
    return kids;
  }
};

			

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

    StringBuilder sb = new StringBuilder().append(root.val).append(",");
    Queue<Node> q = new ArrayDeque<>(Arrays.asList(root));

    while (!q.isEmpty())
      for (int sz = q.size(); sz > 0; --sz) {
        Node node = q.poll();
        if (node.children.isEmpty()) {
          sb.append("n");
        } else {
          for (Node child : node.children) {
            q.offer(child);
            sb.append(child.val).append("#");
          }
        }
        sb.append(",");
      }

    return sb.toString();
  }

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

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

    for (int i = 1; i < vals.length; ++i) {
      Node parent = q.poll();
      final String[] kids = vals[i].split("#");
      List<Node> children = new ArrayList<>();
      for (final String kid : kids) {
        if (kid.equals("n"))
          continue;
        Node child = new Node(Integer.parseInt(kid));
        children.add(child);
        q.offer(child);
      }
      parent.children = children;
    }

    return root;
  }
}