Problem Statement:
Given the root of a binary tree, return the level order traversal of its nodes’ values.. (i.e., from left to right, level by level).
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Explanation:Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Use Depth-First Search (DFS) with
recursionto traverse the binary tree. - Maintain an ans
arraywhere each index represents a level of the tree. - At each node:
- If the
current leveldoesn't exist inans, create a new sub-array. - Push the current node's value to the corresponding level in
ans. - Recursively call the function for the left and right children, increasing the
level by 1.
- If the
- Finally, return the
ansarray containing level-wise node values.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
ans = []
Call traversal(root, 0)
→ curr = 1, level = 0
→ ans[0] doesn't exist → initialize as [] → ans = [[]]
→ ans[0].push(1) → ans = [[1]]
→ curr.left = 2 → call traversal(2, 1)
→ curr = 2, level = 1
→ ans[1] doesn't exist → initialize as [] → ans = [[1], []]
→ ans[1].push(2) → ans = [[1], [2]]
→ curr.left = null → no call
→ curr.right = 4 → call traversal(4, 2)
→ curr = 4, level = 2
→ ans[2] doesn't exist → initialize as [] → ans = [[1], [2], []]
→ ans[2].push(4) → ans = [[1], [2], [4]]
→ curr.left = null → no call
→ curr.right = null → no call
→ Back to curr = 2 → finished
→ Back to curr = 1
→ curr.right = 3 → call traversal(3, 1)
→ curr = 3, level = 1
→ ans[1] exists → ans[1].push(3) → ans = [[1], [2, 3], [4]]
→ curr.left = null → no call
→ curr.right = null → no call
→ Back to curr = 1 → finished
Traversal complete.
Final ans: [[1], [2, 3], [4]]
Output: Result: [[1], [2, 3], [4]]
var levelOrder = function(root) {
if(!root) return [];
let ans = [];
let traversal = (curr, level) => {
if(!ans[level]) ans[level] = [];
ans[level].push(curr.val);
curr.left && traversal(curr.left, level + 1);
curr.right && traversal(curr.right, level + 1);
}
traversal(root, 0);
return ans;
};
class Solution:
def levelOrder(self, root):
ans = []
def dfs(node, level):
if not node:
return
if len(ans) == level:
ans.append([])
ans[level].append(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
dfs(root, 0)
return ans
class Solution {
public List> levelOrder(TreeNode root) {
List> ans = new ArrayList<>();
dfs(root, 0, ans);
return ans;
}
private void dfs(TreeNode node, int level, List> ans) {
if (node == null) return;
if (ans.size() == level) {
ans.add(new ArrayList<>());
}
ans.get(level).add(node.val);
dfs(node.left, level + 1, ans);
dfs(node.right, level + 1, ans);
}
}
class Solution {
public:
void dfs(TreeNode* node, int level, vector>& ans) {
if (!node) return;
if (ans.size() == level) ans.push_back({});
ans[level].push_back(node->val);
dfs(node->left, level + 1, ans);
dfs(node->right, level + 1, ans);
}
vector> levelOrder(TreeNode* root) {
vector> ans;
dfs(root, 0, ans);
return ans;
}
};
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEVELS 100
#define MAX_NODES_PER_LEVEL 100
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int ans[MAX_LEVELS][MAX_NODES_PER_LEVEL];
int count[MAX_LEVELS] = {0};
void dfs(TreeNode* node, int level) {
if (!node) return;
ans[level][count[level]++] = node->val;
dfs(node->left, level + 1);
dfs(node->right, level + 1);
}
public class Solution {
public void DFS(TreeNode node, int level, List> ans) {
if (node == null) return;
if (ans.Count == level) ans.Add(new List());
ans[level].Add(node.val);
DFS(node.left, level + 1, ans);
DFS(node.right, level + 1, ans);
}
public IList> LevelOrder(TreeNode root) {
var ans = new List>();
DFS(root, 0, (List>)ans);
return ans;
}
}
