[c++] Easy to understand, one approach to solve Zigzag & Level order traversal
This approch can be used to solve both level order traversal & zig zag traversal.\nIt\'s easy to start with the level order traversal. I hope the comments are c
This approch can be used to solve both level order traversal & zig zag traversal.\nIt\'s easy to start with the level order traversal. I hope the comments are clear.\n\n```\nvector<vector<int>> levelOrder(TreeNode* root) {\n        if (!root) return {}; // return if root is null\n        queue<TreeNode*> q;\n        q.push(root); //push the root node.\n        vector<vector<int>> out; //result vector\n      \n\t\t /*\n\t\t * Idea is to create a vector for every level based on the queue size.\n\t\t * eg: if a level has four elements say 1, 2, 3, 4 -> Then create a vector of size 4.\n\t\t * \n\t\t * note: size of the queue is computed before the loop, so that we don\'t consider \n\t\t * newly pushed elements.\n\t\t */\n\t\t \n        while (!q.empty()) {\n            \n            int sz = q.size(); /* current queue size */\n            vector<int> curr(sz); /* vector of size sz */\n\t\t\t\t\t\t\n            for (int i = 0; i < sz; i++) {\n                TreeNode* tmp = q.front();\n                q.pop();\n                curr[i] = tmp->val; /* insert to the correct index */\n\t\t\t\t\n\t\t\t\t/* Add the left & right nodes to the queue in the loop. */\n                if (tmp->left) q.push(tmp->left);\n                if (tmp->right) q.push(tmp->right);\n            }\n            out.push_back(curr); /* once the level is done, push the vector to output vector. */\n        }\n        return out;\n    }\n```\n\nThe same idea can be extended to zig-zag traversal. The only difference would be, if we are on an even level (say second level)** insert into the vector from end. Odd levels insert from beginning.**\n```\n\nvector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        \n        if (!root) return {};\n        \n        queue<TreeNode*> q;\n        vector<vector<int>> out;\n            \n        q.push(root);  \n        int level = 0; /* to alternate levels, or a bool variable */\n        \n        while (!q.empty()) {\n            \n            int sz = q.size();  \n            vector<int> curr(sz); \n            \n            for (int i = 0; i < sz; i++) {\n                \n                TreeNode* tmp = q.front();\n                q.pop();\n                \n                if (level == 0) {\n                    curr[i] = tmp->val; // odd level, insert like 0, 1, 2, 3 etc. \n                } else {\n                    curr[sz - i - 1] = tmp->val; /* even level insert from end. 3, 2, 1, 0. (sz - i - 1) to get the index from end */\n                }\n                \n                if (tmp->left) q.push(tmp->left);\n                if (tmp->right) q.push(tmp->right);\n            }\n            out.push_back(curr); // now push the level traversed to output vector\n            level = !level; // toggle the level using negation. or level == 0 ? level = 1 : level = 0;\n        }\n        return out;\n```\n\nThank you for reading. Please let me your comments/feedback.
['Tree', 'C']