Sharing my 8ms C++ solution


  • 0
    T
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
     
     // implement this using unordered_map and queue (queue for level-order traversal)
    class Solution {
    private:
        unordered_map<int, vector<int>> verticalOrderHelper(TreeNode* root)
        {
            unordered_map<int, vector<int>> myMap;
            if(root==NULL)
                return myMap;
                
            queue<TreeNode*> nodeQueue;
            queue<int> posQueue;
            nodeQueue.push(root);
            posQueue.push(0);
            
            while(nodeQueue.size()>0)
            {
                TreeNode* node = nodeQueue.front();
                nodeQueue.pop();
                int pos = posQueue.front();
                posQueue.pop();
                myMap[pos].push_back(node->val);
                if(node->left)
                {
                    nodeQueue.push(node->left);
                    posQueue.push(pos-1);
                }
                if(node->right)
                {
                    nodeQueue.push(node->right);
                    posQueue.push(pos+1);
                }
            }
            
            return myMap;
        }
        
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> result;
            if(root==NULL)
                return result;
            
            unordered_map<int, vector<int>> myMap = verticalOrderHelper(root);
            
            int minPos = INT_MAX;
            int count=0;
            for(auto x=myMap.begin(); x!=myMap.end(); x++)
            {
                minPos = min(minPos, x->first);
                count++;
            }
            
            result.resize(count);
            for(auto y=myMap.begin(); y!=myMap.end(); y++)
            {
                result[y->first-minPos] = y->second;
            }
            
            return result;
        }
    };

Log in to reply
 

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