题解 | BM26 求二叉树的层序遍历

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder(root) {
    // write code here
    let ans = [];
    // 层序遍历函数
    function levelOrder(node, ans) {
        if (node == null) {
            return ans;
        }
        // 第一层
        ans.push([node.val]);
        // 定义遍历的节点队列
        let query = [];
        if (node.left) {
            // 向队列中添加左节点
            query.push({ node: node.left, level: 1 });
        }
        if (node.right) {
            // 向队列中添加右节点
            query.push({ node: node.right, level: 1 });
        }
        while (query.length) {
            // 取出队列第一个节点
            let cur = query[0];
            // 弹出第一个节点
            query = query.slice(1);
            // console.log("query:", query);
            // console.log("cur:", cur);
            let level = cur.level;
            // 判断ans数组当前层是否有数据
            if (ans[level]) {
                // 有数据，则直接数组追加即可
                ans[level].push(cur.node.val);
            } else {
                // 没有数据，则需要初始化数组
                ans[level] = [cur.node.val];
            }
            if (cur.node.left) {
                // 向队列中添加左节点
                query.push({ node: cur.node.left, level: level + 1 });
            }
            if (cur.node.right) {
                // 向队列中添加右节点
                query.push({ node: cur.node.right, level: level + 1 });
            }
        }
    }
    levelOrder(root, ans);
    return ans;
}
module.exports = {
    levelOrder: levelOrder
};