🎨Now live: Try our Free AI Image Generation Feature

Description
This problem involves traversing a binary tree in level order, which means visiting nodes level by level from left to right.
Intuition
To solve this problem, we can use a queue-based approach. Starting from the root node, we will enqueue each node and process them level by level. We will maintain a list of lists where each inner list represents nodes at a particular level.
Approach
- Initialization: Start with an empty result list to store levels of nodes.
- Breadth-First Traversal: Use a queue to facilitate level-order traversal. - Enqueue the root node. - While the queue is not empty: - Determine the current level size (number of nodes in the current level). - Initialize an empty list to store node values for the current level. - Iterate through the current level nodes (based on the level size): - Dequeue a node from the front of the queue. - Append its value to the current level list. - Enqueue its left and right children if they exist. - Append the current level list to the result list.
- Completion: Once the queue is empty, all nodes have been processed, and the result list contains lists of node values by level.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the binary tree. Each node is processed exactly once.
Space Complexity:
O(N) in the worst case. This occurs when the tree is completely unbalanced, and the queue contains all nodes at the last level.
Code
C++
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> result;
if (root == nullptr) return result;
queue queue;
queue.push(root);
while (!queue.empty()) {
int levelSize = queue.size();
vector currentLevel;
for (int i = 0; i < levelSize; i++) {
TreeNode* currentNode = queue.front();
queue.pop();
currentLevel.push_back(currentNode->val);
if (currentNode->left != nullptr) queue.push(currentNode->left);
if (currentNode->right != nullptr) queue.push(currentNode->right);
}
result.push_back(currentLevel);
}
return result;
}
};
Python
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
Java
class Solution {
public List> levelOrder(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) return result;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
currentLevel.add(currentNode.val);
if (currentNode.left != null) queue.add(currentNode.left);
if (currentNode.right != null) queue.add(currentNode.right);
}
result.add(currentLevel);
}
return result;
}
}
JavaScript
var levelOrder = function(root) {
let result = [];
if (root === null) return result;
let queue = [root];
while (queue.length > 0) {
let levelSize = queue.length;
let currentLevel = [];
for (let i = 0; i < levelSize; i++) {
let currentNode = queue.shift();
currentLevel.push(currentNode.val);
if (currentNode.left !== null) queue.push(currentNode.left);
if (currentNode.right !== null) queue.push(currentNode.right);
}
result.push(currentLevel);
}
return result;
};