LeetCode 102: Binary Tree Level Order Traversal (BFS Queue)
LeetCode 102TreeBFSToday we solve LeetCode 102 - Binary Tree Level Order Traversal.
Source: https://leetcode.com/problems/binary-tree-level-order-traversal/
English
Problem Summary
Given the root of a binary tree, return its node values level by level from left to right.
Key Insight
“Level order” is exactly breadth-first traversal. Use a queue and process nodes in batches by current queue size to separate levels.
Brute Force and Limitations
A DFS approach can still work if we track depth and append to ans[depth]. It is valid, but BFS queue matches the problem statement more directly and is easier to reason about by levels.
Optimal Algorithm Steps
1) If root is null, return empty list.
2) Push root into queue.
3) While queue not empty, read current size k.
4) Pop exactly k nodes to form one level, and push their children.
5) Append current level to result and continue.
Complexity Analysis
Time: O(n) where n is number of nodes.
Space: O(n) in worst case for queue + output.
Common Pitfalls
- Not snapshotting queue size before iterating one level.
- Mixing nodes from next level into current level.
- Forgetting null checks before pushing children.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
level.add(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
ans.add(level);
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
queue := []*TreeNode{root}
ans := make([][]int, 0)
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
ans = append(ans, level)
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = (int)q.size();
vector<int> level;
level.reserve(size);
for (int i = 0; i < size; ++i) {
TreeNode* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
ans.push_back(move(level));
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def levelOrder(self, root):
if not root:
return []
q = deque([root])
ans = []
while q:
size = len(q)
level = []
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var levelOrder = function(root) {
if (!root) return [];
const q = [root];
const ans = [];
while (q.length) {
const size = q.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = q.shift();
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(level);
}
return ans;
};中文
题目概述
给定二叉树根节点，按层从左到右返回每一层的节点值。
核心思路
层序遍历本质就是 BFS。使用队列，按“当前队列长度”分层处理即可。
暴力解法与不足
也可以用 DFS + 深度参数，把节点放入 ans[depth]。可行，但在“按层处理”这个目标下，BFS 的语义和实现更直观。
最优算法步骤
1）根节点为空直接返回空数组。
2）根节点入队。
3）循环直到队列为空，每轮先记录当前层节点数 k。
4）弹出 k 个节点组成一层，并把它们的左右子节点（非空）入队。
5）将该层加入答案。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（队列与结果存储）。
常见陷阱
- 未固定当前层的队列长度，导致层边界混乱。
- 当前层与下一层节点混在一起。
- 子节点判空遗漏导致异常。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
level.add(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
ans.add(level);
}
return ans;
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
queue := []*TreeNode{root}
ans := make([][]int, 0)
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
ans = append(ans, level)
}
return ans
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = (int)q.size();
vector<int> level;
level.reserve(size);
for (int i = 0; i < size; ++i) {
TreeNode* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
ans.push_back(move(level));
}
return ans;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def levelOrder(self, root):
if not root:
return []
q = deque([root])
ans = []
while q:
size = len(q)
level = []
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var levelOrder = function(root) {
if (!root) return [];
const q = [root];
const ans = [];
while (q.length) {
const size = q.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = q.shift();
level.push(node.val);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
ans.push(level);
}
return ans;
};
Comments