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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9def levelOrder(root):
10 if not root:
11 return []
12 result = []
13 queue = deque([root])
14 while queue:
15 level_size = len(queue)
16 level_nodes = []
17 for _ in range(level_size):
18 node = queue.popleft()
19 level_nodes.append(node.val)
20 if node.left:
21 queue.append(node.left)
22 if node.right:
23 queue.append(node.right)
24 result.append(level_nodes)
25 return resultWe use a deque from the collections module to easily append and pop nodes from the queue. Starting with the root node if it is not null, we add it to the queue. For each level, determine the number of nodes at that level (i.e., the size of the queue), then iterate over them, adding each node's children to the queue for the next level. Collect and return the node values in a nested list representing each level.
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 <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13void dfs(TreeNode* node, int level, vector<vector<int>>& levels) {
14 if (!node) return;
15 if (level == levels.size())
16 levels.push_back(vector<int>());
17 levels[level].push_back(node->val);
18 dfs(node->left, level + 1, levels);
19 dfs(node->right, level + 1, levels);
20}
21
22vector<vector<int>> levelOrder(TreeNode* root) {
23 vector<vector<int>> levels;
24 dfs(root, 0, levels);
25 return levels;
26}Invoke the DFS function recursively by starting at the root node. We use a vector of vectors to represent levels during traversal. For each visited node, determine the current level size and append values to their respective level container, expanding the container list when necessary. Recurse into children while maintaining depth count to achieve the level order.