4ms Concise DFS C++ Implementation


  • 2
    A

    1 Calculate depth in each recursion.
    2 Switch directions for adding current value based on (depth % 2).

      vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> rst;
            traverse(root, 0, rst);
            return rst;
        }
        
    void traverse(TreeNode* root, int depth, vector<vector<int>> & rst) {
        if (!root)
            return;
        if (rst.size() == depth) {
            vector<int> temp;
            rst.push_back(temp);
        }
        if (depth % 2 == 0)   
            rst[depth].push_back(root ->val);
        else{
            rst[depth].insert(rst[depth].begin(), root -> val);   
        }
        traverse(root -> left, depth + 1, rst);  
        traverse(root -> right, depth  +1, rst);
    }

  • 1
    D

    Almost the same idea, but I meet a problem.
    Initially I pass traverse(root, 0, rst) then I use if(rst.size() < depth). Then I got run time error.... could you please look into my problem? Thx!


  • 0
    A

    In the first recursion, rst.size() is 0, depth is 0; If you use "if(rst.size() < depth)", you are accessing rst[0] illegally in the following rst[depth] before initializing rst[0].


  • 0
    D

    Oh sorry, there is a typo. I pass traverse(root, 1, rst). Then got run time error.


  • 0
    A

    The same illegal index accessing problem. This time, you are accessing rst[1] while you only initialized rst[0]. Try using rst[depth -1] instead of rst[depth].


  • 0
    D

    Oh yeah, thanks allenwow~~


  • 0
    K

    great solution, why no upvote


Log in to reply
 

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