Tree BFS

levelOrderBottom.cpp

// Iteration
vector<vector<int> > levelOrderBottom(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q{{root}};
    while (!q.empty()) {
        vector<int> oneLevel;
        for (int i = q.size(); i > 0; --i) { //init i with q.size(), it runs well even if we change the size of q in loop
            TreeNode *t = q.front(); 
            q.pop();
            oneLevel.push_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        res.insert(res.begin(), oneLevel);
    }
    return res;
}

// Recursion
void levelorder(TreeNode* node, int level, vector<vector<int>>& res) {
    if (!node) return;
    if (res.size() == level) res.push_back({}); //apply for new layer
    res[level].push_back(node->val);
    if (node->left) levelorder(node->left, level + 1, res);
    if (node->right) levelorder(node->right, level + 1, res);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> res;
    levelorder(root, 0, res);
    return vector<vector<int>> (res.rbegin(), res.rend());
}