Skip to content

Latest commit

 

History

History
145 lines (114 loc) · 6.41 KB

0102.md

File metadata and controls

145 lines (114 loc) · 6.41 KB
title description keywords
102. 二叉树的层序遍历
LeetCode 102. 二叉树的层序遍历题解,Binary Tree Level Order Traversal,包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
102. 二叉树的层序遍历
二叉树的层序遍历
Binary Tree Level Order Traversal
解题思路
广度优先搜索
二叉树

102. 二叉树的层序遍历

🟠 Medium  🔖  广度优先搜索 二叉树  🔗 力扣 LeetCode

题目

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:

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)

  • 使用队列实现
  1. 首先将根节点放入队列中;
  2. 更新队列的长度 len ,遍历队列的前 len 个节点;
  3. 如果该节点存在直接子节点,将直接子节点加入队列中,并将节点的值存入一个临时数组中;
  4. 将队列的前 len 个节点出队,此时队列中都是下一层的子节点,将临时数组加入返回值中;
  5. 重复步骤 2、3、4,直至队列为空;

思路二:深度优先遍历(DFS)

  1. 维护一个递归函数,参数为节点和该节点的深度
  2. 先将根节点与深度 0 传入递归函数
  3. 将节点放入 index 与深度对应的数组内
  4. 将节点的左子节点和右子节点分别传入递归函数,深度 +1
  5. 重复步骤 3、4,直至子节点为空

代码

::: code-tabs @tab 广度优先遍历(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;
};

@tab 深度优先遍历(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 二叉树的锯齿形层序遍历 [✓] 广度优先搜索 二叉树 🟠 🀄️ 🔗
107 二叉树的层序遍历 II [✓] 广度优先搜索 二叉树 🟠 🀄️ 🔗
111 二叉树的最小深度 [✓] 深度优先搜索 广度优先搜索 1+ 🟢 🀄️ 🔗
314 二叉树的垂直遍历 🔒 深度优先搜索 广度优先搜索 3+ 🟠 🀄️ 🔗
429 N 叉树的层序遍历 广度优先搜索 🟠 🀄️ 🔗
637 二叉树的层平均值 [✓] 深度优先搜索 广度优先搜索 1+ 🟢 🀄️ 🔗
993 二叉树的堂兄弟节点 [✓] 深度优先搜索 广度优先搜索 1+ 🟢 🀄️ 🔗
2471 逐层排序二叉树所需的最少操作数目 [✓] 广度优先搜索 二叉树 🟠 🀄️ 🔗
2493 将节点分成尽可能多的组 广度优先搜索 并查集 🔴 🀄️ 🔗