题解 | #26.求二叉树的层序遍历#

抄的题解

递归(前序遍历)

主要思路：前序遍历，中、左、右

左边的节点一定先于右边节点遍历到，加入至对应的数组中，满足层序遍历的要求；

要点：

1、利用一个level变量标记当前递归的深度，将节点的值push到当前深度的数组的后面；

2、level变量大于res数组的size，说明第一次进入二叉树本层，对res扩容；

扩展：

前序：中、左、右

中序：左、中、右

后续：左、右、中

三种遍历都是左边节点一定比右边节点先遍历到，那么push_back至对应深度的数组次序也一定与层次遍历一致；所以针对此方法，中序、后序一样可以实现层次遍历。

对示例1模拟前序遍历，如下图所示：

function levelOrder( root ) {
  function preOrder(root,level){
    if(root==null)
      return;
    if (level >= res.length)
      res.push([]);
    res[level].push(root.val);
    preOrder(root.left,level+1);
    preOrder(root.right,level+1);
  }
  let res = [];
  preOrder(root,0);
  return res;
}
module.exports = {
    levelOrder : levelOrder
};