题目地址
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
题目描述
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
思路
这道题可以借助队列实现，首先把root入队，然后入队一个特殊元素Null(来表示每层的结束)。
然后就是while(queue.length), 每次处理一个节点，都将其子节点（在这里是left和right）放到队列中。
然后不断的出队， 如果出队的是null，则表式这一层已经结束了，我们就继续push一个null。
关键点解析
-
队列
-
队列中用Null(一个特殊元素)来划分每层
-
树的基本操作- 遍历 - 层次遍历（BFS）
-
注意塞入null的时候，判断一下当前队列是否为空，不然会无限循环
代码
/*
* @lc app=leetcode id=102 lang=javascript
*
* [102] Binary Tree Level Order Traversal
*
* https://leetcode.com/problems/binary-tree-level-order-traversal/description/
*
* algorithms
* Medium (47.18%)
* Total Accepted: 346.4K
* Total Submissions: 731.3K
* Testcase Example: '[3,9,20,null,null,15,7]'
*
* Given a binary tree, return the level order traversal of its nodes' values.
* (ie, from left to right, level by level).
*
*
* For example:
* Given binary tree [3,9,20,null,null,15,7],
*
*
* 3
* / \
* 9 20
* / \
* 15 7
*
*
*
* return its level order traversal as:
*
* [
* [3],
* [9,20],
* [15,7]
* ]
*
*
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const items = []; // 存放所有节点
const queue = [root, null]; // null 简化操作
let levelNodes = []; // 存放每一层的节点
while (queue.length > 0) {
const t = queue.shift();
if (t) {
levelNodes.push(t.val)
if (t.left) {
queue.push(t.left);
}
if (t.right) {
queue.push(t.right);
}
} else { // 一层已经遍历完了
items.push(levelNodes);
levelNodes = [];
if (queue.length > 0) {
queue.push(null)
}
}
}
return items;
};
相关题目
书籍推荐
