A C++ DFS solution, clean and well commented

  • 0

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

    class Solution {
        // 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;
            // 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);
        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);
            return res;

Log in to reply

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