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] ]
Classic solution for BFS problem is to use two queues. One for current level, and the other for next level. This method is to visit tree level by level. Time complexity is O(n), space cost is O(n), n is the number of nodes in tree.
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<List<Integer>> levelOrder(TreeNode root) { 12 List<List<Integer>> result = new ArrayList<List<Integer>>(); 13 if (root == null) 14 return result; 15 Deque<TreeNode> current = new ArrayDeque<TreeNode>(); 16 Deque<TreeNode> next; 17 TreeNode tmpNode; 18 current.addLast(root); 19 while (current.size() > 0) { 20 // Refresh next queue 21 next = new ArrayDeque<TreeNode>(); 22 List<Integer> tmpList = new ArrayList<Integer>(); 23 while (current.size() > 0) { 24 tmpNode = current.pop(); 25 if (tmpNode.left != null) 26 next.addLast(tmpNode.left); 27 if (tmpNode.right != null) 28 next.addLast(tmpNode.right); 29 tmpList.add(tmpNode.val); 30 } 31 // Refresh prev queue 32 current = next; 33 result.add(tmpList); 34 } 35 return result; 36 } 37 }
Binary Tree Level Order Traversal 解答
原文：http://www.cnblogs.com/ireneyanglan/p/4834085.html