A C++ DFS solution, clean and well commented

• I know there are many good BFS solutions, just here to provide a DFS one

``````class Solution {
private:
// first int : col of this node, second int : row of this node
// vector<int> : stores vals of nodes at this (row, col), use vector because may have 2 nodes of the same (row, col)
map<int, map<int, vector<int>>> m;
// dfs traverse the tree, add val to corresponding position of map
void helper(TreeNode* node, int row, int col) {
if(!node) return;
m[col][row].push_back(node->val);
// this order make sure if two nodes are in the same row and column, the order should be from left to right.
if(node->left) helper(node->left, row+1, col-1);
if(node->right) helper(node->right, row+1, col+1);
}
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
helper(root, 0, 0);
vector<vector<int>> res;
// add vals of each col
for(auto itr = m.begin(); itr != m.end(); ++itr) {
vector<int> tmp;
// add vals of each (row, col)
for(auto it = itr->second.begin(); it != itr->second.end(); ++it) {
for(int& i : it->second) tmp.push_back(i);
}
res.push_back(tmp);
}
return res;
}
};
``````

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