Binary Tree Level Order Traversal II Solutions in C++

// Source : https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
// Author : Hao Chen
// Date   : 2014-06-27



/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        queue<TreeNode*> q;
        vector< vector<int> > vv;
        vector<int> v;
        if (root){
            v.push_back(root->val);
            vv.push_back(v);
        }
        q.push(root);
        int i=0;
        vector<TreeNode*> vt;
        while(q.size()>0){
            TreeNode *p = q.front();
            q.pop();
            vt.push_back(p);
            if ( p==NULL ) {
                continue;
            }
            q.push(p->left);
            q.push(p->right);
        }
    
    
        int step = 2;
        int j;
        for (int i=1; i<vt.size(); i=j ){
            v.clear();
    
            int cnt=0;
            for (j=i; j<i+step && j<vt.size(); j++){
                if (vt[j]) {
                    v.push_back(vt[j]->val);
                    cnt += 2;
                }
            }
            step = cnt;
            if (v.size()>0) {
                vv.push_back(v);
            }
        }
        //reverse the order
        reverse(vv.begin(), vv.end());
        return vv;
    }
};

#include <vector>
using std::vector;

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        levelOrderBottom(root, 0);
        return vector<vector<int> >(vec_.rbegin(), vec_.rend());
    }

private:
    void levelOrderBottom(TreeNode *root, int level) {
        if (root == NULL) return;
        if (vec_.size() == level) vec_.push_back({root->val});
        else vec_[level].push_back(root->val);
        levelOrderBottom(root->left, level+1);
        levelOrderBottom(root->right, level+1);
    }

private:
    vector<vector<int> > vec_;
};

/// Source : https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>

using namespace std;

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// BFS
/// Time Complexity: O(n), where n is the number of nodes in the tree
/// Space Complexity: O(n)
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {

        vector<vector<int>> res;
        if(root == NULL)
            return res;

        queue<pair<TreeNode*,int>> q;
        q.push(make_pair(root, 0));

        while(!q.empty()){

            TreeNode* node = q.front().first;
            int level = q.front().second;
            q.pop();

            if(level == res.size())
                res.push_back(vector<int>());
            assert( level < res.size() );

            res[level].push_back(node->val);
            if(node->left)
                q.push(make_pair(node->left, level + 1 ));
            if(node->right)
                q.push(make_pair(node->right, level + 1 ));
        }

        reverse(res.begin(), res.end());
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>

using namespace std;

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// BFS
/// No need to store level information in the queue :-)
///
/// Time Complexity: O(n), where n is the number of nodes in the tree
/// Space Complexity: O(n)
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {

        vector<vector<int>> res;
        if(root == NULL)
            return res;

        queue<TreeNode*> q;
        q.push(root);
        int level_num = 1;

        while(!q.empty()){

            int new_level_num = 0;
            vector<int> level;
            for(int i = 0; i < level_num; i ++){
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);

                if(node->left){
                    q.push(node->left);
                    new_level_num ++;
                }
                if(node->right){
                    q.push(node->right);
                    new_level_num ++;
                }
            }

            res.push_back(level);
            level_num = new_level_num;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};


int main() {

    return 0;
}