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

Question

问题描述

题目是对一个对象中的value属性做遍历求和， 对象结构如下：

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)

用DFS和BFS求解

Answer 1

首先说一下BFS 广度优先搜索算法和DFS 深度优先搜索算法。
此题的两种搜索算法分别实现如下：

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则是层层递进的逻辑。
所以如果结果是一个集合，那么集合中项的顺序是不同的。
此例中，结果是唯一求和值，所以2种算法对结果并无影响。

性能

由于路径的不同，将导致求和顺序的不同。但是，不管哪种算法，所经历项的总数是相同的。

我们常常能看到一个普遍的结论是，BFS的性能要优于DFS。为什么会有这个结论呢？
首先，需要明白的是这2种算法的第3个字母S表示的是什么意思。S代表的是Search，所以这2种算法是针对搜索而言的，而搜索是无须遍历每一项的。如果数据离散度较高，那么使用BFS更能容易命中，而实际生活种，数据总是离散的，所以往往BFS要比DFS更快。
可是，如果只是更快，未必就是更好。而且考虑到遍历所有数据样本的情况，为什么仍然会有BFS优于DFS的结论呢？
要说这个，首先看一下这2种算法的实现。DFS是递归的方法，性能开销在于函数调用栈的出入栈；BFS是队列的方法，性能开销在于内存申请，队列的出入。这是两者本质的区别。在不考虑内存限制的情况下，内存的操作会略快一点，但要视不同语言而定，但两者的差距并没有想象中的那么大。而在内存限制的情况下，其实BFS要增加额外的内存管理成本，反而得不偿失。
另一点在于，BFS因为有着第三者队列的存在，所以在多进程模型下，可以将队列分片，交由不同的进程处理。而DFS由于不知其深度，无法很好地平均分配，即使分片了，也仍然存在DFS的问题。

因此，结论往往是BFS要优于DFS。

然而Javascript不一样！

虽然Javascript有办法做到多进程和多线程，但是其开销比静态语言要大的多。因为VM的执行机制，只有当其翻译到fork新进程的时候才会去优化代码和执行，所以会慢很多。而在浏览器端，虽然可以利于Worker做到多进程，但是其创建和通信的成本仍然巨大。所以就目前而言，BFS的多进程优势对于Javascript并不适用。
在此题中，因为结果是需要唯一确定的值，而且必须经历所有节点，所以BFS和DFS的性能差异其实就是2种算法的性能开销的博弈。在ES6+之前，每次调用函数必须为函数创建额外的执行上下文，由于执行上下文是在函数执行时动态赋予的，所以在函数申明和定义时无法优化；但是ES6的箭头函数在函数定义时指定了上下文，因此避免了额外的开销。另外，ES6还有一个特性是尾调用优化（虽然目前只有Safari支持），但是尾调用优化的本质就是VM内部自动优化，避免了DFS的出入栈问题。所以，对于Javascript更快。

不过，实践是检验的唯一标准，上面的都是理论，实际结果比理论更重要。
我在自己电脑上跑了一下，此题的DFS解法比BFS解法，在Chrome下要快1倍，在Safari下要快40%（看来V8还是厉害）。你也可以自己试验一下。

不要人云亦云，实践出真知，亲身实践比任何理论都有说服力。而且技术是不断进步的，如果理论只是维持不变，或者片面，总会被淘汰的。

---

最后，给些类递归的新奇解法吧。

Proxy

"use strict";

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

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

    const proxied = new Proxy(node, {
      get(target, key, receiver) {
        switch (key) {
          case Symbol.toPrimitive:
            return () =>
              receiver.children.reduce(
                (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));

类似的，可以用ES5的getter实现。

JSON

"use strict";

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

解决问题是唯一目标

我在面试时，往往会遇到一些令人哭笑不得但又确实很有效的解答。但只要解决问题就好啦，最实用的才是最好的。

就此题而言，可以看出，其value不管是在多深的层级，其实都是连续递增的。所以单就此题而言，完全可以变成求从1到最大的value值的和。所以，只要找到最大的value值，就可以计算了，而不必遍历所有节点。

Answer 2

典型的层级遍历。与按层输出二叉树的节点思路相同。

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));

Answer 3

首先说一下所有用递归可以解决的问题都可以用循环替代。

• 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 ]

从遍历顺序中可以看出来差别。

Answer 4

采用广度优先遍历。

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)
        }
    }
    return total
}

Answer 5

  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();
      }
    }
  }