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,#,#,15,7}
,
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
public class Solution { public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<TreeNode> current = new ArrayList<TreeNode>(); if(root != null) current.add(root); while(!current.isEmpty()){ ArrayList<TreeNode> nextlevel = new ArrayList<TreeNode>(); ArrayList<Integer> list= new ArrayList<Integer>(); for(TreeNode n:current){ list.add(n.val); if(n.left !=null) nextlevel.add(n.left); if(n.right !=null) nextlevel.add(n.right); } current = nextlevel; result.add(list); } return result; } }
learned: when do traversal between two levels in tree, make sure build new list to store node in each level