Binary Tree Zigzag Level Order Traversal - LeetCode

PHOTO EMBED

Sat May 29 2021 16:56:05 GMT+0000 (UTC)

Saved by @Randumkeng

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> dq;
        if(root)dq.push(root);
        int flag = 0;
        while(!dq.empty()){
            vector<int> curlvl;
            int size = dq.size();
			// traverse all the nodes of current level
            for(int s=0; s<size; s++){
                root = dq.front(); dq.pop();
                if(flag)
                    curlvl.insert(curlvl.begin(), root->val);
                else
                    curlvl.push_back(root->val);
                if(root->left)
					dq.push(root->left);
                if(root->right)
					dq.push(root->right);
            }
            flag^=1;
            ans.push_back(curlvl);
        }
        return ans;
    }
};
content_copyCOPY

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/