Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
Example : Given binary tree
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Also think about a version of the question where you are asked to do a level order traversal of the tree when depth of the tree is much greater than number of nodes on a level.
Solution:
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public ArrayList<ArrayList<Integer>> levelOrder(TreeNode A) { Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(A); ArrayList<ArrayList<Integer>> result = new ArrayList<>(); while (!queue.isEmpty()) { int size = queue.size(); ArrayList<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i ++) { TreeNode curr = queue.poll(); level.add(curr.val); if (curr.left != null) { queue.offer(curr.left); } if (curr.right != null) { queue.offer(curr.right); } } result.add(level); } return result; } }