leetcode------Binary Tree Level Order Traversal

标题：	Binary Tree Level Order Traversal
通过率：	29.9%
难度：	简单

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},

return its level order traversal as:[

  [3],
  [9,20],
  [15,7]
]

做了这道题感觉二叉树的知识还是很弱的，这个点确实要加强，整体思路就是分层遍历，利用一个队列进行处理，但是到底再哪一层这个问题需要处理。
　　刚开始我想到了。满二叉树每层都是固定的，那么我往队列里面放元素时每层我都放满，即，再第二层时应该往队列里面放两个节点，但是会出现左右一个是空，那么如果是空我就放一个为-1的节点，这些就把满二叉树放满了。在读取的时候用math.pow（2，num）每层读取这么多，如果读到不是-1的节点就向list中存值，这么做程序是没有问题的但是出现了超时的问题，也就是说，深度越深我要读的东西越多，增加了运行时间，然后我就想每一层数量是变动的，那么我用一个计数器来计算下下一层中我往队列中放了几个节点，那么在读取的时候我就读取几个节点就行了。等于说广度遍历一遍数组就完成了。时间复杂度就是一个O（n），这个算法应该是时间复杂度最低的算法，然后我实验后发现确实是一个时间复杂度最低的做法。
　　在网上查资料时我查到了以下几种做法：（时间复杂度都没有我想的这个高）
1、用两个队列处理，放下一层元素时把下一层元素放在另外一个队列中，例如，我在读取q1时，我把下层要遍历的元素放在q2中，下一次读取q2往q1中放元素，交替执行两层循环，增加了额外空间。
2、先算出树的深度，然后利用深度一层一层去读，这个时间复杂度是O（n^2）


下面先贴出我超时的一个算法（构造满二叉树）：

 1 /**
 2  * Definition for binary tree
 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         LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
14         int num=0,i=1;
15         TreeNode tree=null;
16         if(root==null) return result;
17         queue.addLast(root);
18         while(!queue.isEmpty()){
19             List<Integer> tmp=new ArrayList<Integer>();
20             for(i=1;i<=Math.pow(2, num);i++){
21                 if(!queue.isEmpty()){
22                     tree=queue.removeFirst();
23                     if(tree.val!=-1)
24                         tmp.add(tree.val);
25                     if(tree.left!=null)
26                         queue.addLast(tree.left);
27                     if(tree.left==null)
28                     {
29                         TreeNode treer=new TreeNode(-1);
30                         queue.addLast(treer);
31                     }
32                     if(tree.right!=null)
33                         queue.addLast(tree.right);
34                     if(tree.right==null)
35                     {   
36                         TreeNode treer=new TreeNode(-1);
37                         queue.addLast(treer);
38                     }
39                 }
40                 else break;
41             }
42             result.add(tmp);
43         }
44         return result;
45     }
46 }

然后我进行改进只算我放了几个进去的代码：

 1 /**
 2  * Definition for binary tree
 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         LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
14         int count=1,level=0;
15         if(root==null) return result;
16         queue.addLast(root);
17         while(!queue.isEmpty()){
18             level=0;
19             List<Integer> tmp=new ArrayList<Integer>();
20             for(int i=0;i<count;i++){
21                 TreeNode tree=queue.removeFirst();
22                 tmp.add(tree.val);
23                 if(tree.left!=null){
24                     queue.addLast(tree.left);
25                     level++;
26                 }
27                 if(tree.right!=null){
28                     queue.addLast(tree.right);
29                     level++;
30                 }
31             }
32             result.add(tmp);
33             count=level;
34         }
35         return result;
36        
37     }
38 }