Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return
[
[3],
[9,20],
[15,7]
] For the problem given I decided to use BFS, however, the trick is to remember the number of nodes in same level before traversal.
So utilizing queue.size() before remove all the nodes in the same level. Utilized ArrayList to implement the queue. See code below:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
if (root == null ){
return result;
}
BFS(root,result);
return result;
}
/*At first I was trying to use BFS but I have no idea how to get all nodes in same layer to outputh to one list until I saw some answer from jiuzhang suanfa. It is obviously that the number of nodes is the queue's size before offerl()
implemented the queue by using linkedList*/
public void BFS (TreeNode root, ArrayList<ArrayList<Integer>> lists) {
ArrayList<TreeNode> queue = new ArrayList<TreeNode> ();
queue.add(root);
int maxDepth=0;
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<Integer>();
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode curr = queue.remove(0);
list.add(curr.val);
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
lists.add(list);
}
} }