102. Binary Tree Level Order Traversal
102. Binary Tree Level Order Traversal
题目
Given the root
of a binary tree, return the level order traversal of its nodes ' values. (i.e., from left to right, level by level).
Example 1:
![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]
. -1000 <= Node.val <= 1000
题目大意
给你二叉树的根节点 root
,返回它节点值的 层序 遍历。(即逐层地,从左到右访问所有节点)。
解题思路
思路一:广度优先遍历(BFS)
- 使用队列实现
- 首先将根节点放入队列中;
- 更新队列的长度
len
,遍历队列的前len
个节点; - 如果该节点存在直接子节点,将直接子节点加入队列中,并将节点的值存入一个临时数组中;
- 将队列的前
len
个节点出队,此时队列中都是下一层的子节点,将临时数组加入返回值中; - 重复步骤 2、3、4,直至队列为空;
思路二:深度优先遍历(DFS)
- 维护一个递归函数,参数为节点和该节点的深度
- 先将根节点与深度 0 传入递归函数
- 将节点放入 index 与深度对应的数组内
- 将节点的左子节点和右子节点分别传入递归函数,深度 +1
- 重复步骤 3、4,直至子节点为空
代码
广度优先遍历(BFS)
// 思路一:广度优先遍历(BFS)
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
let res = [];
if (root == null) return res;
let queue = [root];
while (queue.length) {
let len = queue.length;
let temp = [];
for (let i = 0; i < len; i++) {
if (queue[i].left) queue.push(queue[i].left);
if (queue[i].right) queue.push(queue[i].right);
temp.push(queue[i].val);
}
queue = queue.slice(len);
res.push(temp);
}
return res;
};
深度优先遍历(DFS)
// 思路二:深度优先遍历(DFS)
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
let res = [];
const traverse = (node, deep) => {
if (node == null) return;
if (res.length == deep) {
res[deep] = [node.val];
} else {
res[deep].push(node.val);
}
traverse(node.left, deep + 1);
traverse(node.right, deep + 1);
};
traverse(root, 0);
return res;
};
相关题目
相关题目
- [103. 二叉树的锯齿形层序遍历](./0103.md)
- [107. 二叉树的层序遍历 II](./0107.md)
- [111. 二叉树的最小深度](./0111.md)
- [🔒 Binary Tree Vertical Order Traversal](https://leetcode.com/problems/binary-tree-vertical-order-traversal)
- [637. 二叉树的层平均值](./0637.md)
- [429. N 叉树的层序遍历](https://leetcode.com/problems/n-ary-tree-level-order-traversal)
- [993. 二叉树的堂兄弟节点](https://leetcode.com/problems/cousins-in-binary-tree)
- [2471. 逐层排序二叉树所需的最少操作数目](https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level)
- [2493. 将节点分成尽可能多的组](https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups)