题目：

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]]

 

confused what "{1,#,2,3}" means? 

链接： 

题解：

层序遍历二叉树。使用BFS, 用一个Queue来辅助存储当前层的节点。

Time Complexity - O(n)， Space Complexity - O(n) (最多一层节点数)

public class Solution {    public ArrayList
     
      
       > levelOrder(TreeNode root) {        ArrayList
       
        
         > result = new ArrayList
         
          
           >(); if(root == null) return result; Queue
           
             queue = new LinkedList
            
             (); ArrayList
             
               list = new ArrayList
              
               (); queue.add(root); int curLevel = 1, nextLevel = 0; while(!queue.isEmpty()){ TreeNode node = queue.poll(); curLevel --; list.add(node.val); if(node.left != null){ queue.offer(node.left); nextLevel ++; } if(node.right != null){ queue.offer(node.right); nextLevel ++; } if(curLevel == 0){ curLevel = nextLevel; nextLevel = 0; result.add(new ArrayList
               
                (list)); list.clear(); } } return result; }}
               
              
             
            
           
          
         
        
       
      
     

 

Update:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > levelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if(root == null)            return res;        Queue
         
           queue = new LinkedList<>();         //BFS        ArrayList
          
            list = new ArrayList<>(); queue.add(root); //Initialize int curLevel = 1, nextLevel = 0; while(!queue.isEmpty()) { TreeNode node = queue.poll(); list.add(node.val); curLevel --; if(node.left != null) { queue.offer(node.left); nextLevel++; } if(node.right != null) { queue.offer(node.right); nextLevel++; } if(curLevel == 0) { curLevel = nextLevel; nextLevel = 0; res.add(new ArrayList
           
            (list)); list.clear(); } } return res; }}
           
          
         
        
       
      
     

 

 二刷:

使用一个queue来帮助BFS层序遍历，有两个记录当前层节点和下一层节点数的变量curLevel以及nextLevel。

Java:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > levelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if (root == null) {            return res;        }        Queue
         
           q = new LinkedList<>();        q.offer(root);        int curLevel = 1, nextLevel = 0;        List
          
            list = new ArrayList<>(); while (!q.isEmpty()) { TreeNode node = q.poll(); curLevel--; list.add(node.val); if (node.left != null) { q.offer(node.left); nextLevel++; } if (node.right != null) { q.offer(node.right); nextLevel++; } if (curLevel == 0) { curLevel = nextLevel; nextLevel = 0; res.add(new ArrayList
           
            (list)); list.clear(); } } return res; }}
           
          
         
        
       
      
     

 

三刷:

不要忘记把结果保存到结果集里，并且也要clear当前层。

Java:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > levelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if (root == null) {            return res;        }        List
         
           level = new ArrayList<>();        Queue
          
            q = new LinkedList<>(); q.offer(root); int curLevel = 1, nextLevel = 0; while (!q.isEmpty()) { TreeNode node = q.poll(); curLevel--; level.add(node.val); if (node.left != null) { q.offer(node.left); nextLevel++; } if (node.right != null) { q.offer(node.right); nextLevel++; } if (curLevel == 0) { curLevel = nextLevel; nextLevel = 0; res.add(new ArrayList
           
            (level)); level.clear(); } } return res; }}
           
          
         
        
       
      
     

 

Update: 换种写法

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public List
     
      
       > levelOrder(TreeNode root) {        List
       
        
         > res = new ArrayList<>();        if (root == null) return res;        Queue
         
           q = new LinkedList<>();        q.offer(root);        int curLevel = 1;        List
          
            list = new ArrayList<>(); while (!q.isEmpty()) { TreeNode node = q.poll(); curLevel--; list.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); if (curLevel == 0) { curLevel = q.size(); res.add(new ArrayList<>(list)); list.clear(); } } return res; }}
          
         
        
       
      
     

 

 

Reference:

https://leetcode.com/discuss/21778/java-solution-using-dfs

https://leetcode.com/discuss/22533/java-solution-with-a-queue-used

https://leetcode.com/discuss/58454/java-queue-solution-beats-100%25