Given a binary tree, return the level order traversal of its nodes' values. (i.e, from left to right, level by level).
Constraints
Approach
Links
YouTube
Examples
Input: [3, 9, 20, null, null, 15, 7]
Output:
[
[3],
[9, 20],
[15, 7]
]
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity : O(N) since each node is processed exactly once.
* Space complexity : O(N) to keep the output structure which contains N
* node values.
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList = new ArrayList();
if(root != null) {
helper(resultList, root, 0);
}
return resultList;
}
private void helper(List<List<Integer>> resultList,
TreeNode node,
int level) {
// start the current level
if(resultList.size() == level) {
resultList.add(new ArrayList<Integer>());
}
// fulfil the current level
resultList.get(level).add(node.val);
// process child nodes for the next level
if(node.left != null) {
helper(resultList, node.left, level+1);
}
if(node.right != null) {
helper(resultList, node.right, level+1);
}
}
}
/**
* Time complexity : O(N) since each node is processed exactly once.
* Space complexity : O(N) to keep the output structure which contains N
* node values.
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList = new ArrayList();
if(root != null) {
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
int level = 0;
while(!queue.isEmpty()) {
// start the current level
resultList.add(new ArrayList<Integer>());
// number of elements in the current level
int noOfNodes = queue.size();
for(int i = 0; i < noOfNodes; i++) {
TreeNode node = queue.remove();
resultList.get(level).add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
// go to next level
level++;
}
}
return resultList;
}
}
