Share my 6ms C++ recursive solution, O(1) space


  • -1
    H

    class Solution {
    public:
    void zigzagLevelOrderUtil(vector<vector<int>> &ret, TreeNode *root, int level) {
    if (!root) return;

        if (level == ret.size()) {
            ret.push_back(vector<int>(1, root -> val));
        }
        else {
            if (level % 2) 
                ret[level].insert(ret[level].begin(), root -> val);
            else
                ret[level].push_back(root -> val);
        }
        
        zigzagLevelOrderUtil(ret, root -> left, level + 1);
        zigzagLevelOrderUtil(ret, root -> right, level + 1);
    }
    
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> ret;
        zigzagLevelOrderUtil(ret, root, 0);
        return ret;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.