一道JS树状对象遍历算法题,求解?

问题描述

今天去面试,题目是对一个对象中的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算法,但我看完后依然觉得需要用到递归,很苦恼,各路大神能否帮忙解答一下?

阅读 422
评论 2019-09-06 提问
    5 个回答
    Suieu
    • 542

    首先说一下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并不适用。
    在此题中,因为结果是需要唯一确定的值,而且必须经历所有节点,所以BFSDFS的性能差异其实就是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值,就可以计算了,而不必遍历所有节点。

    评论 赞赏 2019-09-06

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

      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));
      评论 赞赏 2019-09-06
        鸿则
        • 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 ]

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

        评论 赞赏 2019-09-06
          小九
          • 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)
                  }
              }
              return total
          }
          评论 赞赏 2019-09-06
              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();
                  }
                }
              }
            评论 赞赏 2019-09-06
              撰写回答

              登录后参与交流、获取后续更新提醒