Tree-E-102. Binary Tree Level Order Traversal

时间 20180301

1.解法1

  本题的实质是广度优先搜索BFS，而队列可以轻松的以迭代形式实现它，不过不同于BFS的是，层序便利需要在队列中记住每一层的分割点，而BFS不关心层数只要遍历到指定元素就行了。为了记住这个分割点，我们在进入下一层之前先记下这一层的元素个数N(N其实就是当前queue的大小)，然后只遍历N个节点（展开下一层节点的同时queue中会新加入很多下下一层的节点）。遍历完N个节点后记录新的层数，在进入下一层。对于II，反悔的层是逆序的，我们只要在结果中，每次把下面新一层加到当前这一层的前面就可以了。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //BFS的广度优先算法
        //这里使用到队列先进先出“先插入”
        //错误的写法：List is abstract; cannot be instantiated
        //List<List<Integer>> res = new List<List<Integer>>(); 
        //ArrayList与LinkedList的区别？？？
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        //错误的写法new Queue<TreeNode>();
        // Queue<TreeNode> q = new Queue<TreeNode>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        
        if(root != null)q.add(root);
        
        while(!q.isEmpty()){
            //每个List中都是一个List
            List<Integer> level = new LinkedList<Integer>();
            //用来保存当前层中的TreeNode的个数
            int size = q.size();
            for(int i = 0; i < size; i++){
                root = q.poll();
                level.add(root.val);
                //错误没有异常处理条件if(root.left!=null)
                // q.offer(root.left);
                // q.offer(root.right);
                //queue有offer方法？
                if(root.left != null){
                    q.add(root.left);
                }
                if(root.right != null){
                    q.add(root.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

class Solution {
   public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //区别list=null和List<Integer> list = new LinkedList<Integer>();list为空的区别。？？？？
       List<List<Integer>> res = new LinkedList<List<Integer>>();
       //List<Integer> level = new LinkedList<Integer>();
       
       Queue<TreeNode> q = new LinkedList<TreeNode>();
       if(root!=null){
          q.add(root); 
       }
       
       while(!q.isEmpty()){
           //level = null;
           List<Integer> level = new LinkedList<Integer>();
           int size = q.size();
           // while(size>=0){
           //     TreeNode head =  q.poll();
           //     level.add(head.val);
           //     if(head.left != null) q.add(head.left);
           //     if(head.right != null) q.add(head.right);
           //     size--;
           // }
           for(int i = 0;i<size;i++){
               TreeNode head = q.poll();
               level.add(head.val);
               if(head.left != null)q.add(head.left);
               if(head.right != null) q.add(head.right);
           }
           res.add(0,level);
       }
       
       
       
       return res;
   }
   
   
}