15 lines concise and easy understand c++ solution both recursive and iteration version


  • 0
    A

    Recursive version:

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> res;
            dfs(res, root, 0);
            for(int i = 0; i < res.size(); i++)
                if(i % 2) reverse(res[i].begin(), res[i].end());
            return res;
        }
        void dfs(vector<vector<int>>& res, TreeNode* root, int level){
            if(root){
                if(res.size() <= level) res.push_back(vector<int> ());
                res[level].push_back(root->val);
            }else return;
            dfs(res, root->left, level + 1);
            dfs(res, root->right, level + 1);
        }
    };
    

    Iterative version:

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            if(!root) return {};
            queue<TreeNode*> que;
            que.push(root);
            vector<vector<int>> res;
            bool lefttoright = true;
            while(!que.empty()){
                int size = que.size();
                vector<int> row(size, 0);
                for(int i = 0; i < size; i++){
                    TreeNode* tmp = que.front();
                    que.pop();
                    int index = lefttoright ? i : size - i - 1;
                    row[index] = tmp->val;
                    if(tmp->left) que.push(tmp->left);
                    if(tmp->right) que.push(tmp->right);
                }
                lefttoright = !lefttoright;
                res.push_back(row);
            }
            return res;
        }
    };

Log in to reply
 

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