(￣▽￣)” 太久没练手了，都生疏了

用到的知识点明显是 BFS ，可能上课的时候有讲过层序遍历，但我已经忘得一干二净了，巩固基础吧，太菜了。

方法一：BFS 迭代

思路：对一棵二叉树进行层序遍历，可用迭代的方式实现，将根节点放入一个辅助队列中，然后不断遍历队列。

步骤：

1. 首先特殊判断，是否为空树。
2. 然后创建一个答案数组，一个辅助队列，将根节点放入辅助队列
3. 对队列进行遍历，直至队列为空
4. 对队列的头部结点进行弹出并保存其值，将其值保存在一个区别各层间数据的辅助数组
5. 判断这个结点的左右子结点是否存在，若存在即将其弹入队列的尾部
6. 重复 4，5 步

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (!root) return []
    let res = []
    let queue = [root]
    while (queue.length) {  // 遍历直至辅助队列为空
        let len = queue.length
        let level_res = []
        for (let i = 0; i < len; i++) {
            let temp = queue.shift()   // 将辅助队列头部弹出并保存
            if (temp.left) queue.push(temp.left)  // 判断左右子结点是否存在
            if (temp.right) queue.push(temp.right)
            level_res.push(temp.val)
        }
        res.push(level_res)
    }
    return res
};
复制代码

方法二：DFS 递归

思路：（看了解析之后结合自己的理解）带着一个 index （标记层数）标签去先序遍历整个二叉树，每次都将二叉树的数据按照 index 区分开来。

var levelOrder = function (root) {
    if(!root) return [] // 特殊判断
    let res=[[]]   // 特定给根节点保留一个数组层
    DFS(root,res,0)  // DFS 入口
    return res
};

var DFS = function(node,res,index){
    if(!node) return    // 如果结点为空，返回
    if(res.length<=index) res.push([])    // 提前插入一层数组，避免"of null"
    res[index].push(node.val)   // 开始先序遍历，插入对应的层数
    DFS(node.left,res,index+1)  // 左子树遍历
    DFS(node.right,res,index+1) // 右子树遍历
}
复制代码

明显感觉 DFS 的代码更简洁，因为 DFS 隐含地调用了一个栈结构，不需要自己维护。

时间复杂度都为 O(N)