# 一道JS树状对象遍历算法题，求解？

### 问题描述

``````var nodes = {
value: 1,
children: [
{
value:2,
children:[
{
value:4,
children:[...]
},
{
value:3,
children:[...]
},
...
]
},
{
value:5,
children:[...]
},
...
]
}
``````

``````function sum(node){
if(node.children.length===0){
return node.value
}
else{
return node.children.reduce(
(prev, curr) => prev + sum(curr),
node.value
)
}
}
sum(nodes)
``````

5 个回答
Suieu
• 542

BFS

``````"use strict";

const sum = (nodes, result = 0) => {
const stack = [nodes];
while (stack.length) {
const { value = 0, children } = stack.pop();
result += value;
if (children) stack.push(...children);
}
return result;
};``````

DFS

``````"use strict";

const sum = ({ value = 0, children = [] }) =>
children.reduce((result, node) => result + sum(node), value);``````

#### 区别

##### 路径

`递归下去，回溯上来`，这就是`DFS`的简单逻辑。而`BFS`则是`层层递进`的逻辑。

#### 然而Javascript不一样！

##### Proxy
``````"use strict";

const proxy = (() => {
const store = new WeakMap();

return node => {
if (store.has(node)) return store.get(node);

const proxied = new Proxy(node, {
switch (key) {
case Symbol.toPrimitive:
return () =>
(result, node) => result + node,
target.value || 0
);
case "children": {
const children = target[key];
return Array.isArray(children) ? children.map(proxy) : [];
}
default:
return target[key];
}
}
});
store.set(node, proxied);
return proxied;
};
})();

console.log(+proxy(nodes));``````

##### JSON
``````"use strict";

const sum = eval(JSON.stringify(nodes).replace(/\D+/g, "+") + "0");
console.log(sum);``````

#### 解决问题是唯一目标

``````var nodes = {
value: 1,
children: [
{
value:2,
children:[
{
value:4,
},
{
value:3,
},
]
},
{
value:5,
},
]
}

function sum(nodes) {
let s = 0;
let level = [nodes];
let nextLevel = [];
while (level.length > 0) {
for (let i = 0; i < level.length; i++) {
s += level[i].value;
if ("children" in level[i]) {
nextLevel = nextLevel.concat(level[i].children);
}
}

level = nextLevel;
nextLevel = [];
}

return s;
}

console.log(sum(nodes));``````

• 1.7k

• BFS：广度优先搜索
• DFS：深度优先搜索

BFS 的重点在于队列，而 DFS 的重点在于递归。

``````namespace A {
export interface Node {
value: number,
children: Array<Node>,
};
}

const nodes: Array<A.Node> = [
{
value: 1,
children: [
{
value: 2,
children: [
{
value: 3,
children: [],
},
{
value: 4,
children: [],
},
],
},
{
value: 5,
children: [],
},
{
value: 6,
children: [
{
value: 7,
children: [],
},
],
},
],
},
{
value: 8,
children: [
{
value: 9,
children: [],
},
{
value: 10,
children: [],
},
],
},
];

function bfs(nodes: Array<A.Node>) {
const queue = new Array(...nodes);
const result = new Array();
while(queue.length) {
const node = queue.shift();
result.push(node.value);
queue.push(...node.children);
}
return result;
}

function dfs(nodes: Array<A.Node>) {
const result = new Array();
nodes.forEach(node => {
result.push(node.value);
result.push(...dfs(node.children));
});
return result;
}

console.log(`bfs:`, bfs(nodes));
console.log(`dfs:`, dfs(nodes));``````

``````bfs: [ 1, 8, 2, 5, 6, 9, 10, 3, 4, 7 ]
dfs: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]``````

• 387

``````function breadthFirstTraverse(nodes = {}) {
let total = 0
let curNode = null
const queue = [nodes]
while (queue.length) {
curNode = queue.pop()
total += curNode.value || 0
if (curNode.children) {
queue.push(...curNode.children)
}
}
}``````

``````  var nodes = {
value: 1,
children: [
{
value: 2,
children: [
{
value: 3,
children: [],
},
{
value: 4,
children: [],
},
],
},
{
value: 5,
children: [],
},
{
value: 6,
children: [
{
value: 7,
children: [],
},
],
},
],
};

function dfs(node) {
var queue = [];
queue.push({
node: node,
index: -1,
});
queue.last = function() {
return this[this.length - 1];
};
let sum = 0;

while (queue.length) {
let last = queue.last();

if (last.index === -1) {
sum += last.node.value;
}

let children = last.node.children;

if (children && children.length) {
if (last.index >= children.length - 1) {
queue.pop();
continue;
}
queue.push({
node: children[++last.index],
index: -1,
});
} else {
queue.pop();
}
}
}``````