Problem
Design serialize and deserialize methods for a binary tree. Encode to a string, decode back to identical tree.
Example
Input: [1,2,3,null,null,4,5]
Output: "1,2,#,#,3,4,#,#,5,#,#"Solution
Pre-order traversal with markers for null nodes. Deserialize using a recursive consumer of tokens.
class Codec:
def serialize(self, root):
def helper(node):
if not node: return ['#']
return [str(node.val)] + helper(node.left) + helper(node.right)
return ','.join(helper(root))
def deserialize(self, data):
tokens = iter(data.split(','))
def helper():
val = next(tokens)
if val == '#': return None
node = TreeNode(int(val))
node.left = helper()
node.right = helper()
return node
return helper()function serialize(root) {
const out = [];
function helper(node) {
if (!node) { out.push('#'); return; }
out.push(node.val);
helper(node.left);
helper(node.right);
}
helper(root);
return out.join(',');
}
function deserialize(data) {
const tokens = data.split(',');
let i = 0;
function helper() {
if (tokens[i] === '#') { i++; return null; }
const node = { val: Number(tokens[i++]), left: null, right: null };
node.left = helper();
node.right = helper();
return node;
}
return helper();
}class Codec {
void serializeHelper(TreeNode* node, string& s) {
if (!node) { s += "#,"; return; }
s += to_string(node->val) + ",";
serializeHelper(node->left, s);
serializeHelper(node->right, s);
}
TreeNode* deserializeHelper(istringstream& iss) {
string val;
getline(iss, val, ',');
if (val == "#") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = deserializeHelper(iss);
node->right = deserializeHelper(iss);
return node;
}
public:
string serialize(TreeNode* root) { string s; serializeHelper(root, s); return s; }
TreeNode* deserialize(string data) { istringstream iss(data); return deserializeHelper(iss); }
};public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
helper(root, sb);
return sb.toString();
}
private void helper(TreeNode node, StringBuilder sb) {
if (node == null) { sb.append("#,"); return; }
sb.append(node.val).append(',');
helper(node.left, sb);
helper(node.right, sb);
}
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
return build(q);
}
private TreeNode build(Queue<String> q) {
String val = q.poll();
if (val.equals("#")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = build(q);
node.right = build(q);
return node;
}
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Pre-order with null markers preserves the structure unambiguously. The deserializer consumes tokens in the same order they were produced.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?