LeetCode 107. 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,null,null,15,7],
3
/
9 20
/
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

大意：从叶子结点到根节点，从左到右每层层序遍历。
解答：两种方法

方法一：队列，和层序遍历类似。只是最后插入方法的区别。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL)
            return res;
        std::queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int nums = q.size();
            vector<int> v;
            for (int i = 0; i < nums; i++){
                TreeNode* node = q.front();
                q.pop();
                v.push_back(node->val);
                if (node->left != NULL)
                    q.push(node->left);
                if (node->right != NULL)
                    q.push(node->right);
            }
            res.insert(res.begin(),v);
        }
        return res;
    }
};

注解：

1. vector中insert的用法：vec.insert(vec.begin()+i,a);//在第i+1个元素前面插入a;

方法二：递归。和层序遍历相同，只是返回答案从后往前返回。（199题）

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int> > res;
        levelorder(root, 0, res);
        return vector<vector<int> > (res.rbegin(), res.rend()); //反向输出res
    }
    void levelorder(TreeNode *root, int level, vector<vector<int> > &res) {
        if (!root) return;
        //因为level从0开始，所以是等于。等于就申请空间
        if (res.size() == level) res.push_back({});
        res[level].push_back(root->val);
        if (root->left) levelorder(root->left, level + 1, res);
        if (root->right) levelorder(root->right, level + 1, res);
    }
};

注解：