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? 

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}".

思路：这道题是二叉树的层次遍历算法，简单来说就是借用队列来实现二叉树的层次遍历，使用循环方法。每次将一层的结点放入队列中，将一层的结点遍历其左右结点，然后pop这一层的结点。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      
        > levelOrder(TreeNode *root) {        vector
       
        
          > result;        queue
         
           pTree;        if(root==NULL)            return result;        pTree.push(root);        int count=1;        vector
          
            temp; while(!pTree.empty()) { temp.clear(); int temp_count=0; for(int i=0;i
           
            val); if(tn->left!=NULL) { pTree.push(tn->left); temp_count++; } if(tn->right!=NULL) { pTree.push(tn->right); temp_count++; } } count=temp_count; result.push_back(temp); } return result; }};
           
          
         
        
       
      
     

看了其他人的思路，使用递归方法实现的：

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private:    vector
     
      
        > result;    public:    void traversal(TreeNode *root,int depth)    {        if(root==NULL)            return;        if(result.size()>depth)        {            result[depth].push_back(root->val);        }        else        {            vector
       
         data;            data.push_back(root->val);            result.push_back(data);        }        traversal(root->left,depth+1);        traversal(root->right,depth+1);    }    vector
        
         
           > levelOrder(TreeNode *root) {                result.clear();        traversal(root,0);        return result;    }};