Lintcode---二叉树的层次遍历

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

您在真实的面试中是否遇到过这个题？

Yes

样例

给出一棵二叉树 {3,9,20,#,#,15,7},

按照从下往上的层次遍历为：

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


思路：二叉树的层次遍历思路，借助队列来实现。相当于广度优先搜索，使用队列（深度优先搜索的话，使用栈）。

     
       若根节点为空，直接返回；

       若根节点非空，则将根节点入队，然后，判断队列是否为空，若不为空，则将队首节点出队，访问，并判断其左右子节点是否为空，若不为空，则压入队列。


       因最终输出是从最后一层到第一层的输出，所以，直接调用reverse()函数，将整个容器翻转就可以了。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 
 
class Solution {
    /**
     * @param root : The root of binary tree.
     * @return : buttom-up level order a list of lists of integer
     */
    /*
    思路：二叉树的层次遍历思路，借助队列来实现，因最终输出是从最后一层到第一层的输出，
    
          所以，直接调用reverse()函数，将整个容器翻转就可以了。
    */
public:
    vector<vector<int>> levelOrderBottom(TreeNode *root) {
        // write your code here
        vector<vector<int>> vec;
        if(root==NULL){
            return vec;
        }
        
        queue<TreeNode*> que;
        que.push(root);
        
        while(!que.empty()){
            
            int count=que.size();
            vector<int> vec_temp;
            
            while(count--){
                TreeNode* temp=que.front();
                que.pop();
                vec_temp.push_back(temp->val);
                
                if(temp->left){
                    que.push(temp->left);
                }
                
                if(temp->right){
                    que.push(temp->right);
                }
            }
            vec.push_back(vec_temp);
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};