-
Notifications
You must be signed in to change notification settings - Fork 0
/
postOrderTraversal.js
68 lines (67 loc) · 2.35 KB
/
postOrderTraversal.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
const defaultLeafFunc = (result, node) => {
result.name = node.name;
};
const defaultParentPostFunc = (result, node) => {
result.name = node.name;
};
const defaultParentPreFunc = (result, node) => {
// result.name = node.name;
};
const defaultAddDepth = (result, parentNode, children) => {
if (!parentNode.hasOwnProperty(children)) {
result.depth = 0;
} else {
result.depth = parentNode.depth + 1;
}
};
function postOrderTraversal(build, {
children = 'children',
leafFunc = defaultLeafFunc,
parentPostFunc = defaultParentPostFunc,
parentPreFunc = defaultParentPreFunc,
addDepth = defaultAddDepth
} = {}) {
let node = build;
const result = {};
const mapResult = [result];
const stack = [];
while (node) {
if (Array.isArray(node[children]) && node[children].length > 0) {
const result = {children: []};
addDepth(result, mapResult[0], children);
parentPreFunc(result, node);
if (!mapResult[0].hasOwnProperty(children)) {
Object.assign(mapResult[0], result);
} else {
mapResult[0].children.push(result);
mapResult.unshift(result);
}
stack.unshift({node, index: 0});
node = node.children[0];
} else {
const nodeResult = {};
addDepth(nodeResult, mapResult[0], children);
leafFunc.apply(null, [nodeResult, node, mapResult[0]]); // leaf-func
if (!mapResult[0].hasOwnProperty(children)) {
Object.assign(mapResult[0], nodeResult);
return result;
}
mapResult[0].children.push(nodeResult);
while (stack[0].index === stack[0].node.children.length - 1) {
parentPostFunc.apply(null, [mapResult[0], stack[0].node]);
stack.shift();
mapResult.shift();
if (stack.length === 0) {
return result;
}
}
node = stack[0].node.children[++stack[0].index];
}
}
return result;
}
module.exports = postOrderTraversal;
module.exports.traversal = postOrderTraversal;
module.exports.defaultLeafFunc = defaultLeafFunc;
module.exports.defaultParentPostFunc = defaultParentPostFunc;
module.exports.defaultParentPreFunc = defaultParentPreFunc;