Serialize and Deserialize Binary Tree
Design a way to turn a binary tree into a string and back:
serialize(root)returns a string describing the tree.deserialize(data)takes that string and returns the root of a tree that is identical to the original, with the same shape and the same values at every position.
The format is up to you, as long as deserialize needs nothing except the string serialize produced. Node values may be negative or repeat. The tree may be empty.
The tests call roundTrip(root), which must return the pair [serialize(root), deserialize(serialize(root))]. A test passes when the first item is a string and the second is a tree equal to the input. In JavaScript the starter has serialize and deserialize stubs and the roundTrip wiring already written; in Python, define all three functions yourself.
Constraints
- The tree has between
0and10^4nodes. -1000 <= Node.val <= 1000
Examples
Example 1
Input: root = [1,2,3,null,null,4,5] Output: ["(any single string)",[1,2,3,null,null,4,5]]
Whatever string you invent, deserializing it must rebuild this exact tree (shape and values).
Example 2
Input: root = [] Output: ["(any single string)",[]]
An empty tree must serialize to some string and come back as an empty tree.
Example 3
Input: root = [7] Output: ["(any single string)",[7]]
A single node.
JavaScript you'll use: Strings and characters Stacks, queues and deques Linked list and tree nodes
/** @param {TreeNode} root @return {string} a string that deserialize can turn back into the tree */
function serialize(root) {
}
/** @param {string} data @return {TreeNode} the root of the rebuilt tree (null for an empty tree) */
function deserialize(data) {
}
// The tests call this one. Keep it as is.
function roundTrip(root) {
const text = serialize(root);
return [text, deserialize(text)];
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.