A C++ DFS solution, clean and well commented


  • 0
    L

    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;
        }
    };
    

Log in to reply
 

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