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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7function levelOrder(root) {
8 if (!root) return [];
9 const result = [];
10 const queue = [root];
11 while (queue.length > 0) {
12 const levelSize = queue.length;
13 const levelNodes = [];
14 for (let i = 0; i < levelSize; i++) {
15 const node = queue.shift();
16 levelNodes.push(node.val);
17 if (node.left) queue.push(node.left);
18 if (node.right) queue.push(node.right);
19 }
20 result.push(levelNodes);
21 }
22 return result;
23}In this implementation, we use a simple array to serve as the queue. Begin with the root node in the queue, and process all nodes level by level. For each node, enqueue its children. Capture node values into sub-arrays, which represents each level's output. Finally, return the result containing all levels.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<IList<int>> LevelOrder(TreeNode root) {
13 var levels = new List<IList<int>>();
14 DFS(root, 0, levels);
15 return levels;
16 }
17
18 private void DFS(TreeNode node, int level, List<IList<int>> levels) {
19 if (node == null) return;
20 if (level == levels.Count)
21 levels.Add(new List<int>());
22 levels[level].Add(node.val);
23 DFS(node.left, level + 1, levels);
24 DFS(node.right, level + 1, levels);
25 }
26}This C# example employs a recursive DFS method. Starting from the root, if current depth matches the level count, a new level is added. Each node value is added to its respective level list during traversal. The function recursively processes left and then right children, ensuring nodes are placed in their correct depth-lists.