Binary Tree Level Order Traversal II
Medium · Graphs · Explanation and code example
Breadth-First Search and Reverse
How it works
A queue visits the tree one depth at a time. Save each level in its own list, then reverse the order of the level lists. Values inside a level retain their left-to-right order.
Steps
- Return an empty list for an empty tree.
- Process exactly the current queue length for each level.
- Append the level and reverse all levels at the end.
Complexity
- Time: O(n).
- Space: O(n) including the queue and returned levels.
Things to watch for
- Reverse level order, keeping values within each level in order.
- Capture queue length before adding children.
- An empty tree has no levels.
Python code example
import collections
class Solution:
def levelOrderBottom(self, root: TreeNode | None) -> list[list[int]]:
if not root:
return []
ans = []
q = collections.deque([root])
while q:
currLevel = []
for _ in range(len(q)):
node = q.popleft()
currLevel.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(currLevel)
return ans[::-1]
C++ code example
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> currLevel;
for (int sz = q.size(); sz > 0; --sz) {
TreeNode* node = q.front();
q.pop();
currLevel.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(currLevel);
}
ranges::reverse(ans);
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.