Tree-E-102. Binary Tree Level Order Traversal

時間 20180301

1.解法1

??本題的實質(zhì)是廣度優(yōu)先搜索BFS释涛，而隊列可以輕松的以迭代形式實現(xiàn)它，不過不同于BFS的是衬潦，層序便利需要在隊列中記住每一層的分割點教届，而BFS不關(guān)心層數(shù)只要遍歷到指定元素就行了稀轨。為了記住這個分割點撮慨，我們在進(jìn)入下一層之前先記下這一層的元素個數(shù)N(N其實就是當(dāng)前queue的大小)毛萌，然后只遍歷N個節(jié)點（展開下一層節(jié)點的同時queue中會新加入很多下下一層的節(jié)點）席舍。遍歷完N個節(jié)點后記錄新的層數(shù)布轿，在進(jìn)入下一層。對于II来颤，反悔的層是逆序的汰扭，我們只要在結(jié)果中，每次把下面新一層加到當(dāng)前這一層的前面就可以了福铅。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //BFS的廣度優(yōu)先算法
        //這里使用到隊列先進(jìn)先出“先插入”
        //錯誤的寫法：List is abstract; cannot be instantiated
        //List<List<Integer>> res = new List<List<Integer>>(); 
        //ArrayList與LinkedList的區(qū)別萝毛？？滑黔？
        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>();
            //用來保存當(dāng)前層中的TreeNode的個數(shù)
            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) {
        //區(qū)別list=null和List<Integer> list = new LinkedList<Integer>();list為空的區(qū)別。略荡？庵佣？？汛兜？
       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;
   }
   
   
}