Все привет. Подскажите, как решить задачу с обходом дерева с помощью цикла?
Есть пример задачи:
const tree = [
{
v: 5,
c: [
{
v: 5
},
{
v: 10,
c: [
{
v: 11,
}
]
},
{
v: 11,
c: [
{
v: 12,
c: [
{
v: 5
}
]
}
]
},
]
},
{
v: 5,
c: [
{
v: 7
},
{
v: 12,
c: [
{
v: 11,
}
]
},
{
v: 14,
},
]
}
]
function treeSum(tree) {
if (!tree.length) {
return 0;
}
let sum = 0;
let stack = [];
tree.forEach(node => stack.push(node));
console.log(tree);
while (stack.length) {
let node = stack.pop();
sum += node.v;
if (node.c) {
node.c.forEach(node => stack.push(node));
}
}
return sum;
}
treeSum(tree);
Задача выше решена. И, к примеру, есть схожая структура данных:
const binaryTree = {
value: 1,
left: {
value: 2,
left: {
value: 3,
left: {
value: 4
}
},
right: {
value: 5
}
},
right: {
value: 6,
left: {
value: 7
},
right: {
value: 8
}
}
}
Следуя тому же подходу, очевидно, где-то неправильно.
function treeSum2(tree) {
let stack = [];
const output = [];
Object.keys(tree).forEach(node => {
stack.push(tree[node]);
});
while (stack.length) {
let node = stack.pop();
output.push(node.value);
/*
if (node.left) {
Object.keys(node.left).forEach(node => {
stack.push(node);
});
}
if (node.right) {
Object.keys(node.right).forEach(node => {
stack.push(node);
});
}
*/
}
return output;
}
treeSum2(binaryTree);