My Recursive C++ Solution


  • 0
    K
    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            // m maps from column to another map, which in turn maps row to all node values in that row and that column. These node values are ordered from left to right due to the usage of in-order tree traversal
            map< int, map<int, vector<int> > > m;
            vector<vector<int> > ret;
            inOrderTraverse (root, 1,1, m);
            for (auto e1: m){
                ret.push_back (vector<int>(0));
                for (auto e2: e1.second)                
                    ret.back().insert(ret.back().end(),e2.second.begin(),e2.second.end());
            }
            return ret;
        }
        
        void inOrderTraverse (TreeNode* root, int column,int row, std::map<int,map<int, vector<int> > > & m)
        {
            if (root == nullptr) return;
            m[column][row].push_back(root->val);
            inOrderTraverse (root->left, column-1, row+1, m);        
            inOrderTraverse (root->right, column+1, row+1, m);
        }
    };
    

Log in to reply
 

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