This approach utilizes a queue to perform a Breadth-First Search (BFS) on the binary tree. Starting from the root, traverse each level of the tree and store values of nodes in separate lists for each level. By using a queue, we can efficiently keep track of nodes at the current level and their respective children for the next level.
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(n), as we store all nodes at each level in the queue.
1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10 TreeNode() {}
11 TreeNode(int val) { this.val = val; }
12 TreeNode(int val, TreeNode left, TreeNode right) {
13 this.val = val;
14 this.left = left;
15 this.right = right;
16 }
17}
18
19public class Solution {
20 public List<List<Integer>> levelOrder(TreeNode root) {
21 List<List<Integer>> levels = new ArrayList<>();
22 if (root == null) return levels;
23 Queue<TreeNode> queue = new LinkedList<>();
24 queue.add(root);
25 while (!queue.isEmpty()) {
26 int levelSize = queue.size();
27 List<Integer> level = new ArrayList<>();
28 for (int i = 0; i < levelSize; i++) {
29 TreeNode node = queue.poll();
30 level.add(node.val);
31 if (node.left != null) queue.add(node.left);
32 if (node.right != null) queue.add(node.right);
33 }
34 levels.add(level);
35 }
36 return levels;
37 }
38}Utilizing Java's ArrayList for dynamic arrays and LinkedList as the queue, this solution processes the binary tree by levels. After checking that the root is not null, while the queue isn’t empty, iterate over each level, collecting node values and adding children to the queue for subsequent levels. Append each level's results to the overall list, which is returned at the end.
This approach involves using a Depth-First Search (DFS) where we pass along the current level during the recursive calls. By keeping track of the current depth, we can directly add node values to their appropriate level in our result list, creating new levels in our result list as needed.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(n), considering the space needed for the result and recursive call stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void dfs(struct TreeNode* node, int level, int** result, int* returnSize, int** resultColSizes) {
11 if (!node) return;
12 if (level >= *returnSize) {
13 *returnSize += 1;
14 result[*returnSize - 1] = (int*)malloc(2000 * sizeof(int));
15 (*resultColSizes)[*returnSize - 1] = 0;
16 }
17 result[level][(*resultColSizes)[level]] = node->val;
18 (*resultColSizes)[level] += 1;
19 dfs(node->left, level + 1, result, returnSize, resultColSizes);
20 dfs(node->right, level + 1, result, returnSize, resultColSizes);
21}
22
23int** levelOrder(struct TreeNode* root, int* returnSize, int** resultColSizes) {
24 *returnSize = 0;
25 int** result = (int**)malloc(2000 * sizeof(int*));
26 *resultColSizes = (int*)malloc(2000 * sizeof(int));
27 dfs(root, 0, result, returnSize, resultColSizes);
28 return result;
29}This C implementation makes use of recursive DFS calls. Starting with an empty result array, we traverse the tree. For each node, check if the current level is present in the result array. If not, allocate space for a new level's data. Store node values at their respective levels and recurse into children, incrementing the level parameter. This allows us to collect all nodes according to their levels in the tree.