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},
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ] 使用队列，BFS，加入dummy节点，每遇到一次相当于换一层。使用DFS的话，可以创建辅助函数，辅助函数接受一个level参数记录层数。另外用hashmap储存level和对应节点的list
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) { LinkedList<TreeNode> list = new LinkedList<TreeNode>(); TreeNode dummy = new TreeNode(0); list.add(root); list.add(dummy); ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(root == null) return res; ArrayList<Integer> line = new ArrayList<Integer>(); while(list.size() != 1) { TreeNode tmp = list.poll(); if(tmp.val == 0) { res.add(line); line = new ArrayList<Integer>(); list.add(dummy); } else { line.add(tmp.val); if(tmp.left != null) list.add(tmp.left); if(tmp.right != null) list.add(tmp.right); } } res.add(line);//最后一层在这里加 return res; }
