107. 二叉树的层次遍历 II

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

该题为 102. 二叉树的层次遍历的进阶版。

有关102. 二叉树的层次遍历的题解，请参考429. N叉树的层序遍历，具体思路是一样的，不再赘述。

Solution1（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int> > res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            vector<int> curLayerNodes;
            TreeNode* t;
            while(len--){
                t = q.front();
                q.pop();
                curLayerNodes.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            res.emplace(res.begin(),curLayerNodes);
        }
        return res;
    }
};

Solution2（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        preorder(root,1,res);
        return res;
    }
    
    void preorder(TreeNode* node, int depth, vector<vector<int>> &res){
        if(!node) return;
        if(res.size() < depth){
            vector<int> t;
            t.push_back(node->val);
            res.emplace(res.begin(), t);
        }else{
            res[res.size()-depth].push_back(node->val);
        }
        preorder(node->left, depth+1, res);
        preorder(node->right, depth+1, res);
    }
};

具体思路就是增加一层，就将该层放到头位置。

vector.emplace()配合vector.begin()实现插到头位置。