前言

     今天夜间接到某BAT面试电话，问了些算法的问题，说实话，感觉有点蒙逼，尤其是被问到了节点树遍历的问题。

      对于树形遍历，在平常开发中很少碰到，多数碰到的是对象的深复制，也就想当然的递归调用了，根本没考虑过性能方面的问题。

      当面试官让我用另一种方式进行遍历，还有其他方式?（提示: 模拟栈或队列来实现），what‘s the fuck? I am falling in my mind without idea,

      其实面试要考察的算法是广度遍历，那么咱先从深度遍历也就是递归调用说起。

 

深度遍历

    故名思意，深度即纵向，

 

   

      递归调用的遍历顺序如下:

      ① 父亲

      ② 儿子 ->  孙子 ->  哒了孙 - >..... 

      ③ 姑娘 -> 外孙子 -> ....

      ④ 小儿子 -> ....

-------------代码实现------------
     
   
      
       
       
   
      
   
      
       
       
                  
   
      
     

 

广度遍历

    故名思意，广度即横向，想办一辈儿传一辈儿的（这么说吧，父亲不结婚，那来的儿子，儿子不结婚，哪来的孙子，先让同辈儿人都结婚，然后再轮到下一辈儿，辈儿辈儿这样）

   怎么保证先后顺序呢? 先出生的，先结婚，老一辈都结完了，才能轮到下一辈，我的天啊，队列呀，数组啊，然后明啦.

   队列: 先进先出: 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');

 

两种方式比较：别看广告，看疗效...