给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: ``` 二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] ``` 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 ## 思路 经典模板题,DFS 和 BFS 都可以。 ### DFS 遍历的时候记录一下 level,每次递归都把 level+1,即可获得正确的层级,push 到对应的数组中即可: ```js let levelOrder = function (root) { let res = []; let dfs = (node, level = 0) => { if (!node) return; if (!res[level]) { res[level] = []; } res[level].push(node.val); dfs(node.left, level + 1); dfs(node.right, level + 1); }; dfs(root); return res; }; ``` ### BFS 利用队列,while 中对于每轮的节点开一个 for 循环加入到数组的一层中即可。 ```js /** * @param {TreeNode} root * @return {number[][]} */ let levelOrder = function (root) { if (!root) return []; let ret = []; let queue = [root]; while (queue.length) { let len = queue.length; let level = []; ret.push(level); for (let i = 0; i < len; i++) { let node = queue.shift(); level.push(node.val); if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } return ret; }; ```