题目说明

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]

]

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1

  / \

 2   3

    /

   4

    \

     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

思路

这道题可以这么做：用一个队列来保存每层节点，遍历该层所有节点同时将每个节点加到结果中，同时将每个节点的子女节点用一个list保存下来，遍历完本层节点后，将保存的子女节点加到队列中继续遍历。直到子女节点为空（也就是队列为空）为止

代码

public ArrayList
      
       
        > levelOrder(TreeNode root) {            // Note: The Solution object is instantiated only once and is reused by each test case.            ArrayList
        
         
          > ans=new ArrayList
          
           
            >(); if(root==null) return ans; Queue
            
              list=new LinkedList
             
              (); list.add(root); while(!list.isEmpty()) { ArrayList
              
                levelNodes=new ArrayList
               
                (); ArrayList
                
                  res=new ArrayList
                 
                  (); while(!list.isEmpty()) { TreeNode node=list.poll(); if(node.left!=null) levelNodes.add(node.left); if(node.right!=null) levelNodes.add(node.right); res.add(node.val); } list.addAll(levelNodes); ans.add(res); } return ans; } }