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

分层遍历二叉树，用BFS即可

class Solution {public:    vector
     
      
       > levelOrder(TreeNode* root) {        queue
       
         Q;        vector
        
         
          > ans;        Q.push(root);        while(!Q.empty())        {            int e = Q.size(); //当前层的结束位置            vector
          
            partans; for(int i = 0; i < e; i++) { TreeNode * p = Q.front(); Q.pop(); if(NULL != p) { partans.push_back(p->val); Q.push(p->left); Q.push(p->right); } } if(!partans.empty()) ans.push_back(partans); } return ans; }};
          
         
        
       
      
     

网上DFS的代码：

class Solution {protected:    vector
     
      
       > ans;    void dfs(TreeNode *root, int height){        if (root == NULL)             return;        while (ans.size() <= height)            ans.push_back(vector
       
        ());        ans[height].push_back(root->val);        dfs(root->left, height + 1);        dfs(root->right, height + 1);    }public:    vector
        
         
          > levelOrder(TreeNode* root) {       dfs(root, 0);        return ans;        }};
         
        
       
      
     

 

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree {3,9,20,#,#,15,7},

3   / \  9  20    /  \   15   7

 

return its bottom-up level order traversal as:

[  [15,7],  [9,20],  [3]]

 

跟上面只是顺序变了，加个reverse就行了。