|
1 | 1 | /** |
2 | | - * Time : O(); Space: O() |
| 2 | + * Time : O(N); Space: O(N) |
3 | 3 | * @tag : Tree; Breadth-first Search |
4 | 4 | * @by : Steven Cooks |
5 | 5 | * @date: Jun 10, 2015 |
|
19 | 19 | * [ [3], [9,20], [15,7] ] |
20 | 20 | * |
21 | 21 | ************************************************************************* |
22 | | - * {@link https://leetcode.com/problems/binary-tree-level-order-traversal/V |
| 22 | + * {@link https://leetcode.com/problems/binary-tree-level-order-traversal/} |
23 | 23 | */ |
24 | 24 | package_102_BinaryTreeLevelOrderTraversal; |
25 | 25 |
|
|
34 | 34 | publicclassSolution { |
35 | 35 |
|
36 | 36 | publicList<List<Integer>>levelOrder(TreeNoderoot) { |
37 | | -List<List<Integer>>result =newArrayList<List<Integer>>(); |
| 37 | +List<List<Integer>>res =newArrayList<>(); |
38 | 38 | if (root ==null) { |
39 | | -returnresult; |
| 39 | +returnres; |
40 | 40 | } |
41 | | -Queue<TreeNode>curLevel =newLinkedList<>(); |
42 | | -curLevel.add(root); |
43 | | -while (!curLevel.isEmpty()) { |
44 | | -List<Integer>curList =newArrayList<>(); |
45 | | -Queue<TreeNode>nextLevel =newLinkedList<>(); |
46 | | -while (!curLevel.isEmpty()) { |
47 | | -TreeNodenode =curLevel.poll(); |
48 | | -curList.add(node.val); |
| 41 | +Queue<TreeNode>level =newLinkedList<>(); |
| 42 | +level.offer(root); |
| 43 | +while (!level.isEmpty()) { |
| 44 | +intsz =level.size(); |
| 45 | +List<Integer>levelList =newArrayList<>(); |
| 46 | +for (inti =0;i <sz;i++) { |
| 47 | +TreeNodenode =level.poll(); |
| 48 | +levelList.add(node.val); |
49 | 49 | if (node.left !=null) { |
50 | | -nextLevel.add(node.left); |
| 50 | +level.offer(node.left); |
51 | 51 | } |
52 | 52 | if (node.right !=null) { |
53 | | -nextLevel.add(node.right); |
| 53 | +level.offer(node.right); |
54 | 54 | } |
55 | 55 | } |
56 | | -// go to next level |
57 | | -result.add(curList); |
58 | | -curLevel =nextLevel; |
| 56 | +res.add(levelList); |
59 | 57 | } |
60 | | -returnresult; |
| 58 | +returnres; |
61 | 59 | } |
62 | 60 |
|
63 | 61 | } |