102. Binary Tree Level Order Traversal (Medium)
https://leetcode.com/problems/binary-tree-level-order-traversal/
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
Solutions
1.
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
int maxDepth = maxDepth(root);
// For different layer, allocate an ArrayList to hold the values.
for (int i = 0; i < maxDepth; i++) {
ans.add(new ArrayList<>());
}
recurse(root, 0, ans);
return ans;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
return Math.max(left, right);
}
private void recurse(TreeNode root, int depth, List<List<Integer>> ans) {
if (root == null) {
return;
}
// Apply pre-order visiting method such that values stored in each layer list
// are arranged in the order from left to right.
ans.get(depth).add(root.val);
recurse(root.left, depth + 1, ans);
recurse(root.right, depth + 1, ans);
}
}
2.
class Solution {
// How to define the border of each layer when applying BFS? Count the children nodes
// when traverse the parent nodes.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
// return answer of length 0 if root == null
if (root == null) {
return ans;
}
// Employ queue structure to BFS the tree
Queue<TreeNode> queue = new ArrayDeque<>();
// Insert the root of the tree to initialize the queue.
queue.add(root);
int count = 1;
// Keep the elements visited by BFS order
List<Integer> tmp = new ArrayList<>();
// start BFS
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = count;
for (int i = 0; i < size; i++) {
TreeNode parent = queue.poll();
level.add(parent.val);
count--;
if (parent.left != null) {
queue.add(parent.left);
count++;
}
if (parent.right != null) {
queue.add(parent.right);
count++;
}
}
ans.add(level);
}
// return answer.
return ans;
}
}