My c++ 8ms solution with map, queue and bfs


  • 0
    S

    It's a "bfs search" plus storing all nodes in different vertical level.
    My solution may not be the simplest, but I hope it helps.

    class Solution
    {
    public:
    vector<vector<int>> verticalOrder(TreeNode* root)
    {
    	vector<vector<int>> res;
    	if (!root)
    	{
    		return res;
    	}
    	map<int, vector<int>> mymap;
    	queue<pair<int, TreeNode*>> myqueue;
    	myqueue.push(pair<int, TreeNode*>{0, root});
    	helper(mymap, myqueue);
    	for (map<int, vector<int>>::iterator i = mymap.begin(); i != mymap.end(); i++)
    	{
    		res.push_back(i->second);
    	}
    	return res;
    }
    
    void helper(map<int, vector<int>> &mymap, queue<pair<int, TreeNode*>> &myqueue)
    {
    	while (!myqueue.empty())
    	{
    		pair<int, TreeNode*> temp = myqueue.front();
    		//cout << temp.first << " " << temp.second->val << " " << mystack.size() << endl;
    		myqueue.pop();
    		mymap[temp.first].push_back(temp.second->val);
    		if (temp.second->left)
    		{
    			myqueue.push(pair<int, TreeNode*>{temp.first-1, temp.second->left});
    		}
    		if (temp.second->right)
    		{
    			myqueue.push(pair<int, TreeNode*>{temp.first+1, temp.second->right});
    		}
    	}
    }
    

    };


Log in to reply
 

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