题目

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

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

题解：

乍一看，好像需要很复杂的遍历，需要我们先到最底层，然后再往上整。但是我们会发现这个其实和按层次遍历的结果刚好相反，那么我们可以先按照层次遍历树，然后再将结果取反就行（或者先用一个栈存储结果）。

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    //保存按照层次遍历的结果
    vector<vector<int> > res;
    //存储最终结果
    vector<vector<int> > r;
    //存储每一层的结果
    vector<int> tmp;

    if(root==NULL)
        return res;

    queue<TreeNode* > que;
    que.push(root);
    //记录每层的个数，这样就不用再开一个临时队列存储子节点，而是直接将子节点放到que中
    int i = que.size();

    while(!que.empty())
    {
        TreeNode* head = que.front();
        tmp.push_back(head->val);
        que.pop();
        i--;

        //添加左右子节点
        if(head->left!=NULL)
        {
            que.push(head->left);
        }
        if(head->right!=NULL)
        {
            que.push(head->right);
        }

        //该层遍历结束
        if(i==0)
        {
            res.push_back(tmp);
            tmp.clear();
            i = que.size();
        }
    }

    //将结果取反
    for(int i=res.size()-1;i>=0;i--)
    {
        r.push_back(res[i]);
    }

    return r;
}