Binary Tree Zigzag Level Order Traversal Solutions in C++

// Source : https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
// Author : Hao Chen
// Date   : 2014-07-05



#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;


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

vector<TreeNode*> TreeToArray_level_order(TreeNode* root);

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    if (random()%2){
        return zigzagLevelOrder1(root);
    }
    return zigzagLevelOrder2(root);
}

vector<vector<int> > zigzagLevelOrder1(TreeNode *root) {
    vector<vector<int> > result;
    vector<TreeNode*> tree = TreeToArray_level_order(root);

    int curLevelCnt = 1;
    int nextLevelCnt = 1;
    int level=0;

    for (int i=0; i<tree.size(); i+=curLevelCnt ){
        int cnt=0;
        level++;
        vector<int> v;
        if (level%2==0){
            for(int j=i+nextLevelCnt-1; j>=i; j--){
                if (tree[j]){
                    cnt += 2;
                    v.push_back(tree[j]->val);
                }
            }
        }else{
            for(int j=i; j<i+nextLevelCnt; j++){
                if (tree[j]){
                    cnt += 2;
                    v.push_back(tree[j]->val);
                }
            }
        }
        curLevelCnt = nextLevelCnt;
        nextLevelCnt = cnt;
        if (v.size()>0){
            result.push_back(v);
        }
    }
    return result;
}

vector<TreeNode*> TreeToArray_level_order(TreeNode* root){
    vector <TreeNode*> result;

    queue<TreeNode*> q;
    q.push(root);
    while (q.size()>0) {
        TreeNode* n = q.front();
        q.pop();
        result.push_back(n);
        if (n==NULL){
            //cout << "# ";
            continue;
        }
        //cout << n->val << " ";
        q.push(n->left);
        q.push(n->right);
    }
    //cout << endl;
    return result;
}

vector<vector<int> > zigzagLevelOrder2(TreeNode *root) {
    vector<vector<int> > vv;
    if(root == NULL) return vv;

    int level = 0;
    TreeNode *last = root;
    queue<TreeNode*> q;

    q.push(root);
    vv.push_back(vector<int>());
    while(!q.empty()) {
        TreeNode *p = q.front();
        q.pop();

        vv[level].insert(level%2 ? vv[level].begin() : vv[level].end(), p->val);
        if(p->left) q.push(p->left);
        if(p->right) q.push(p->right);

        if(p == last) {
            level++;
            last = q.back();
            vv.push_back(vector<int>());
        }
    }
    vv.pop_back();

    return vv;
}

void printTree_level_order(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while (q.size()>0){
        TreeNode* n = q.front();
        q.pop();
        if (n==NULL){
            cout << "# ";
            continue;
        }
        cout << n->val << " ";
        q.push(n->left);
        q.push(n->right);
    }
    cout << endl;
}

TreeNode* createTree(int a[], int n)
{
    if (n<=0) return NULL;

    TreeNode **tree = new TreeNode*[n];

    for(int i=0; i<n; i++) {
        if (a[i]==0 ){
            tree[i] = NULL;
            continue;
        }
        tree[i] = new TreeNode(a[i]);
    }
    int pos=1;
    for(int i=0; i<n && pos<n; i++) {
        if (tree[i]){
            tree[i]->left = tree[pos++];
            if (pos<n){
                tree[i]->right = tree[pos++];
            }
        }
    }
    return tree[0];
}

int printMatrix(vector< vector<int> > &vv)
{
    for(int i=0; i<vv.size(); i++) {
        cout << "[";
        for(int j=0; j<vv[i].size(); j++) {
            cout << " " << vv[i][j];
        }
        cout << " ]" << endl;;
    }
}


int main(int argc, char** argv)
{
    TreeNode *p;
    vector< vector<int> > vv;

    int a[] = {3,9,20,0,0,15,7};
    p = createTree(a, sizeof(a)/sizeof(int));
    printTree_level_order(p);
    vv = zigzagLevelOrder(p);
    printMatrix(vv);
    cout << endl;


    return 0;
}

#include <vector>
#include <queue>
#include <cstddef>

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> > zigzagLevelOrder(TreeNode *root) {
		vector<vector<int>> retv;
		if (!root) return retv;
		std::queue<TreeNode*> q; 
		q.push(root);
		bool reverse = false;
		vector<int> v;
		for (int cur_level_sz = 1, next_level_sz = 0; !q.empty(); ) {
			TreeNode *node = q.front(); q.pop();
			v.push_back(node->val); --cur_level_sz;
			if (node->left) { q.push(node->left); ++next_level_sz; }
			if (node->right) { q.push(node->right); ++next_level_sz; }
			if (!cur_level_sz) {
				retv.push_back(reverse ? vector<int>(v.crbegin(), v.crend()) : v); v.clear();
				cur_level_sz = next_level_sz; next_level_sz = 0;
				reverse = !reverse;
			}
		}
		return retv;
    }
};

/// Source : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
/// Author : liuyubobobo
/// Time   : 2019-09-26

#include <iostream>
#include <vector>

using namespace std;


/// BFS
/// Time Complexity: O(n)
/// Space Complexity: O(n)

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


class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        vector<vector<int>> res;
        if(!root) return res;

        vector<TreeNode*> cur;
        cur.push_back(root);
        int index = 0;
        while(cur.size()){

            vector<TreeNode*> next;
            vector<int> tres;

            for(TreeNode* node: cur){
                tres.push_back(node->val);
                if(node->left) next.push_back(node->left);
                if(node->right) next.push_back(node->right);
            }

            if(index % 2) reverse(tres.begin(), tres.end());
            res.push_back(tres);

            cur = next;
            index ++;
        }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
/// Author : liuyubobobo
/// Time   : 2019-09-26

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

using namespace std;


/// BFS
/// Time Complexity: O(n)
/// Space Complexity: O(n)

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


class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        vector<vector<int>> res;
        if(!root) 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;
            if(level >= res.size()) res.push_back({});
            res[level].push_back(node->val);
            q.pop();

            if(node->left) q.push(make_pair(node->left, level + 1));
            if(node->right) q.push(make_pair(node->right, level + 1));
        }

        for(int i = 1; i < res.size(); i += 2)
            reverse(res[i].begin(), res[i].end());
        return res;
    }
};


int main() {

    return 0;
}