LeetCode 107: Binary Tree Level Order Traversal II (Bottom-Up BFS)
LeetCode 107Binary TreeBFSToday we solve LeetCode 107 - Binary Tree Level Order Traversal II.
Source: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
English
Problem Summary
Given the root of a binary tree, return the node values level by level from bottom to top, and each level should still be listed from left to right.
Key Insight
Normal level-order traversal naturally visits levels top-down. We can still do BFS, but either (1) collect top-down and reverse once at the end, or (2) prepend each level into a deque/list-front structure. Both keep correctness simple.
Brute Force and Limitations
DFS can group values by depth with an extra map/list, then emit depths in reverse order. It works but needs depth management. Queue-based BFS is more direct because the problem itself is level-oriented.
Optimal Algorithm Steps (Queue BFS + Final Reverse)
1) If root is null, return empty list.
2) Push root into queue.
3) For each loop, read queue size = current level size.
4) Pop exactly that many nodes, record values, and push children.
5) Append this level to answer.
6) Reverse the answer list once and return.
Complexity Analysis
Time: O(n) for BFS + O(L) level-list reverse (still overall O(n)).
Space: O(n) in worst case for queue + output.
Common Pitfalls
- Mixing nodes from different levels by not freezing current queue size.
- Reversing values inside each level (wrong) instead of reversing level order.
- Forgetting null-root handling.
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>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new ArrayDeque<>();
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);
}
Collections.reverse(ans);
return ans;
}
}/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
q := []*TreeNode{root}
ans := [][]int{}
for len(q) > 0 {
size := len(q)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
level = append(level, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, level)
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
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>> levelOrderBottom(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));
}
reverse(ans.begin(), ans.end());
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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
q = deque([root])
ans = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
ans.reverse()
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 levelOrderBottom = function(root) {
if (root === null) return [];
const q = [root];
const ans = [];
while (q.length > 0) {
const size = q.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = q.shift();
level.push(node.val);
if (node.left !== null) q.push(node.left);
if (node.right !== null) q.push(node.right);
}
ans.push(level);
}
ans.reverse();
return ans;
};中文
题目概述
给定二叉树根节点，要求按层遍历节点值，但输出顺序要从最底层到最顶层；每层内部仍保持从左到右。
核心思路
层序遍历天然是自顶向下。最稳妥做法是先用 BFS 收集所有层，再整体反转层列表。这样每层内部顺序不会被破坏，逻辑也清晰。
基线解法与不足
也可以 DFS 按深度分组，最后按深度倒序输出；但要额外维护深度映射。题目本质是“按层”，队列 BFS 更贴题且不容易出错。
最优算法步骤（队列 BFS + 末尾反转）
1）若根为空，返回空数组。
2）根节点入队。
3）每轮先记录当前队列长度，作为本层节点数。
4）弹出这一层所有节点，收集值，并把左右孩子入队。
5）将本层结果加入答案。
6）遍历结束后整体反转答案并返回。
复杂度分析
时间复杂度：O(n)（BFS 访问每个节点一次，反转层序总量同阶）。
空间复杂度：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>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> q = new ArrayDeque<>();
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);
}
Collections.reverse(ans);
return ans;
}
}/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
q := []*TreeNode{root}
ans := [][]int{}
for len(q) > 0 {
size := len(q)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := q[0]
q = q[1:]
level = append(level, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, level)
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
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>> levelOrderBottom(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));
}
reverse(ans.begin(), ans.end());
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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
q = deque([root])
ans = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
ans.reverse()
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 levelOrderBottom = function(root) {
if (root === null) return [];
const q = [root];
const ans = [];
while (q.length > 0) {
const size = q.length;
const level = [];
for (let i = 0; i < size; i++) {
const node = q.shift();
level.push(node.val);
if (node.left !== null) q.push(node.left);
if (node.right !== null) q.push(node.right);
}
ans.push(level);
}
ans.reverse();
return ans;
};
Comments