-
Notifications
You must be signed in to change notification settings - Fork 44
/
Problem3.js
97 lines (82 loc) · 2.31 KB
/
Problem3.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Problem 3
//
// This problem was asked by Google
//
// Given the root to a binary tree, implement serialize(root), which serializes the tree into a string,
// and deserialize(s), which deserializes the string back into the tree.
//
// For example, given the following Node class
//
// class TreeNode {
// constructor(val, left = null, right = null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
//
// const node = new TreeNode(
// 'root',
// new TreeNode('left', new TreeNode('left.left'), new TreeNode('right'))
// );
// expect(deserialize(serialize(node)).left.left.val).toEqual('left.left'); // Jest Testing
//
// https://leetcode.com/problems/serialize-and-deserialize-bst/
//
// Both serialize and deserialize functions:
// O(N) Time Complexity
// O(N) Space Complexity
// N is the number of nodes in the tree
import TreeNode from '../Data-Structures/TreeNode';
// Serialize using level order traversal
/**
* Returns the serialized string of a tree
* @param {TreeNode} root
* @return {string}
*/
function serialize(root) {
let serializedString = '';
if (root === null) return serializedString;
const queue = [];
queue.push(root);
while (queue.length !== 0) {
const node = queue.shift();
if (node === null) {
serializedString += '* '; // indicates null
} else {
serializedString += `${node.val} `;
queue.push(node.left);
queue.push(node.right);
}
}
return serializedString;
}
/**
* Builds a tree out of a serialized string of a tree
* @param {string} serializedString
* @return {TreeNode}
*/
function deserialize(serializedString) {
if (serializedString.length === 0) return null;
const values = serializedString.split(' ');
values.pop(); // the last value of values will have an empty string due to split
const root = new TreeNode(values[0]);
const queue = [];
queue.push(root);
for (let i = 1; i < values.length; i++) {
const parentNode = queue.shift();
if (values[i] !== '*') {
const leftChild = new TreeNode(values[i]);
parentNode.left = leftChild;
queue.push(leftChild);
}
i++;
if (values[i] !== '*') {
const rightChild = new TreeNode(values[i]);
parentNode.right = rightChild;
queue.push(rightChild);
}
}
return root;
}
export { serialize, deserialize };