Recursion without using reverse(), Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. The given problem is like the level order traversal with a slight change.\nHere, every ev
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->The given problem is like the level order traversal with a slight change.\nHere, every even level is reversed.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInstead of using reverse() function we initialse a variable order which decides whether we goto left child first or the right child first.\nAfter each iteration the order variable is negated.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    int height(TreeNode* root) {\n        if(!root) return 0;\n        int lheight=height(root->left);\n        int rheight=height(root->right);\n        return max(lheight,rheight)+1;\n    }\n    void currentlevel(TreeNode* root,int level,bool order,vector<int>& ans) {\n        if(!root) return;\n        if(level==1) {\n            ans.push_back(root->val);\n            return;\n        }\n        if(order) {\n            currentlevel(root->left,level-1,order,ans);\n            currentlevel(root->right,level-1,order,ans);\n        }\n        else {\n            currentlevel(root->right,level-1,order,ans);\n            currentlevel(root->left,level-1,order,ans);\n        }\n    }\n    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {\n        int h=height(root);\n        vector<vector<int>> res;\n        bool order=true;\n        for(int i=1; i<h+1; i++) {\n            vector<int> ans;\n            currentlevel(root,i,order,ans);\n            res.push_back(ans);\n            order=!order;\n        }\n        return res;\n    }\n};\n```
['Recursion', 'C++']