首頁猿問有沒有人遇到過這個(gè)問題哈！一道JS...

有沒有人遇到過這個(gè)問題哈！一道JS樹狀對(duì)象遍歷算法題，求解？

JavaScript

手掌心 2019-10-08 12:11:04

問題描述今天去面試，題目是對(duì)一個(gè)對(duì)象中的value屬性做遍歷求和，對(duì)象結(jié)構(gòu)如下：varnodes={value:1,children:[{value:2,children:[{value:4,children:[...]},{value:3,children:[...]},...]},{value:5,children:[...]},...]}我當(dāng)時(shí)寫的答案如下functionsum(node){if(node.children.length===0){returnnode.value}else{returnnode.children.reduce((prev,curr)=>prev+sum(curr),node.value)}}sum(nodes)面試官說在數(shù)據(jù)量很大的情況下，用遞歸的性能會(huì)很差，所以這題不能用遞歸，我思前想后都覺得需要用到遞歸，最后只能請(qǐng)教面試官，被他批評(píng)說現(xiàn)在的程序員只會(huì)拍腦袋用遞歸，叫我回去看看DFS和BFS算法，但我看完后依然覺得需要用到遞歸，很苦惱，各路大神能否幫忙解答一下？

查看完整描述

2 回答

泛舟湖上清波郎朗

TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超3個(gè)贊

典型的層級(jí)遍歷。與按層輸出二叉樹的節(jié)點(diǎn)思路相同。varnodes={value:1,children:[{value:2,children:[{value:4,},{value:3,},]},{value:5,},]}functionsum(nodes){lets=0;letlevel=[nodes];letnextLevel=[];while(level.length>0){for(leti=0;is+=level[i].value;if("children"inlevel[i]){nextLevel=nextLevel.concat(level[i].children);}}level=nextLevel;nextLevel=[];}returns;}console.log(sum(nodes));