前言 今天夜間接到某BAT面試電話,問了些演算法的問題,說實話,感覺有點蒙逼,尤其是被問到了節點樹遍歷的問題。 對於樹形遍歷,在平常開發中很少碰到,多數碰到的是對象的深複製,也就想當然的遞歸調用了,根本沒考慮過性能方面的問題。 當面試官讓我用另一種方式進行遍歷,還有其他方式?(提示: 模擬棧或隊列來實 ...
前言
今天夜間接到某BAT面試電話,問了些演算法的問題,說實話,感覺有點蒙逼,尤其是被問到了節點樹遍歷的問題。
對於樹形遍歷,在平常開發中很少碰到,多數碰到的是對象的深複製,也就想當然的遞歸調用了,根本沒考慮過性能方面的問題。
當面試官讓我用另一種方式進行遍歷,還有其他方式?(提示: 模擬棧或隊列來實現),what‘s the fuck? I am falling in my mind without idea,
其實面試要考察的演算法是廣度遍歷,那麼咱先從深度遍歷也就是遞歸調用說起。
深度遍歷
故名思意,深度即縱向,
遞歸調用的遍歷順序如下:
① 父親
② 兒子 -> 孫子 -> 噠了孫 - >.....
③ 姑娘 -> 外孫子 -> ....
④ 小兒子 -> ....
-------------代碼實現------------ <div id="D1" class="D1"> <div class="d1"> <p class="p1"></p> </div> <div class="d2"> <p class="p2"> <i></i> </p> </div> </div> <script> var node = document.getElementById('D1'); function deepInterator(node){ console.log(node); if(node.children.length){ for (var i = 0; i < node.children.length; i++) { deepInterator(node.children[i]); } } } console.time('deepInterator'); deepInterator(node); console.timeEnd('deepInterator'); </script>
廣度遍歷
故名思意,廣度即橫向,想辦一輩兒傳一輩兒的(這麼說吧,父親不結婚,那來的兒子,兒子不結婚,哪來的孫子,先讓同輩兒人都結婚,然後再輪到下一輩兒,輩兒輩兒這樣)
怎麼保證先後順序呢? 先出生的,先結婚,老一輩都結完了,才能輪到下一輩,我的天啊,隊列呀,數組啊,然後明啦.
隊列: 先進先出: push 和 shift 模擬數組
function rangeInterator(node){ var arr = []; arr.push(node); while(arr.length > 0){ node = arr.shift(); console.log(node); if(node.children.length > 0){ for (var i = 0; i < node.children.length; i++){ arr.push(node.children[i]); } } } } console.time('rangeInterator'); rangeInterator(node); console.timeEnd('rangeInterator');
兩種方式比較:別看廣告,看療效...