297. Serialization and deserialization of binary trees
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
Same topic: Sword Points Offer 37. Serialized Binary Tree
- 297. Serialization and deserialization of binary trees
- Question description
- Method 1: Level traversal
- Ideas
- Complexity analysis
- code
- Method 2: Preorder traversal
- Ideas
- Complexity analysis
- code
Title description
Serialization is the operation of converting a data structure or object into continuous bits. The converted data can then be stored in a file or memory, and can also be transmitted to another computer environment through the network. The opposite is done method to reconstruct the original data.
Please design an algorithm to implement serialization and deserialization of binary trees. The execution logic of your sequence/deserialization algorithm is not limited here. You only need to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure.
Example:
You can convert the following binary tree:
1
/ \
twenty three
/ \
4 5
Serialized as "[1,2,3,null,null,4,5]"
Tip: This is consistent with the way LeetCode currently uses it, see LeetCode's format for serializing binary trees for details. You don't have to do this, there are other ways to solve this problem.
Note: Do not use class members/globals/static variables to store state, your serialization and deserialization algorithms should be stateless.
Method 1: Level traversal
Ideas
To reconstruct a binary tree, just record the structure of the original binary tree.
During serialization, you can use hierarchical traversal to record the structure of the tree. Remember to record empty nodes as well.
When deserializing, just use the hierarchical traversal method to terrestrial nodes one by one.
Complexity analysis
serialize()
- time complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes.
- Space complexity:
O
(
q
)
O(q)
O(q), q is the maximum length of the queue, and the worst case is the last level of the full binary tree. At this time, q is of the same order as N, and N is the number of binary tree nodes.
deserialize()
- time complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes.
- Space complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes, and an auxiliary array
nodesis used to store the values of all nodes. The queue space used during hierarchical traversal is q, and the worst case is the same order as N.
Code
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function (root, emptyMarker = '#', seperator = ',') {<!-- -->
if (!root) return '';
const queue = [root];
const arr = [];
// BFS
while (queue.length) {<!-- -->
const node = queue.shift();
if (node) {<!-- -->
arr.push(node.val);
// Even if the child node is empty, it must be listed because the empty node needs to be marked.
queue.push(node.left, node.right);
} else {<!-- -->
// Mark empty nodes
arr.push(emptyMarker);
}
}
//The empty node markers on the right side of the last layer can be deleted
// It doesn’t matter if you don’t delete it `return arr.join(seperator);`
return arr
.join(sperator)
.replace(new RegExp(`(${<!-- -->seperator}${<!-- -->emptyMarker}) + $`), '');
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data, emptyMarker = '#', seperator = ',') {<!-- -->
if (!data) return null;
const nodes = data.split(seperator);
const root = new TreeNode(nodes[0]);
const queue = [root];
let i = 1;
// BFS
while (queue.length) {<!-- -->
const node = queue.shift();
node.left = buildNode(nodes[i]);
node.left & amp; & amp; queue.push(node.left);
i + + ;
node.right = buildNode(nodes[i]);
node.right & amp; & amp; queue.push(node.right);
i + + ;
}
return root;
// *********************************
function buildNode(value) {<!-- -->
return value === void 0 || value === emptyMarker
? null
: new TreeNode(value);
}
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
deserialize() can also use regular expressions to read node values.
JavaScript Code
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data, emptyMarker = '#', seperator = ',') {<!-- -->
const reg = new RegExp(`[^${<!-- -->seperator}] + `, 'g');
let match = reg.exec(data);
if (!match) return null;
const root = new TreeNode(match[0]);
const queue = [root];
while (queue.length) {<!-- -->
const node = queue.shift();
match = reg.exec(data);
if (!match) break;
node.left = buildNode(match[0]);
node.left & amp; & amp; queue.push(node.left);
match = reg.exec(data);
if (!match) break;
node.right = buildNode(match[0]);
node.right & amp; & amp; queue.push(node.right);
}
return root;
// *********************************
function buildNode(value) {<!-- -->
return value === emptyMarker ? null : new TreeNode(value);
}
};
Method 2: Preorder traversal
Ideas
Both preorder traversal and postorder traversal should be possible because the root node can be determined.
serialize
Normal preorder traversal is enough. During the traversal process, the string is assembled and an identifier is added when an empty node is encountered.
deserialize
Build a binary tree in the order of preorder traversal, that is, build the current node first, and then recursively build the left subtree and right subtree.
Complexity analysis
serialize()
- time complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes.
- Space complexity:
O
(
h
)
O(h)
O(h), h is the height of the binary tree.
deserialize()
- time complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes.
- Space complexity:
O
(
N
)
O(N)
O(N), N is the number of binary tree nodes, and
nodesis the space of the array.
Code
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function (root, emptyMarker = '#', seperator = ',') {<!-- -->
if (!root) return '';
let str = '';
preorder(root);
//Remove the last separator
return str.slice(0, -1);
//******************************
function preorder(root) {<!-- -->
if (!root) {<!-- -->
str + = emptyMarker + seperator;
return;
}
str + = root.val + seperator;
preorder(root.left);
preorder(root.right);
}
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data, emptyMarker = '#', seperator = ',') {<!-- -->
if (!data) return null;
const nodes = data.split(seperator);
let i = 0;
return preorder();
// *********************************
function preorder() {<!-- -->
if (i >= nodes.length || nodes[i] === emptyMarker) return null;
const node = new TreeNode(nodes[i]);
i + + ;
node.left = preorder();
i + + ;
node.right = preorder();
return node;
}
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
Summary
The above is all the content of this article. I hope it can be helpful to you and solve the serialization and deserialization problems of binary trees.
If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!
It has been completed, please continue to pay attention. See you next time~