# 4ms Concise DFS C++ Implementation

• 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);
}``````

• 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!

• 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].

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

• 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].

• Oh yeah, thanks allenwow~~

• great solution, why no upvote

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