C++ BFS solution


  • 1
    G
    class Solution {
    public:
    
        vector<vector<int>> verticalOrder(TreeNode* root) 
        {
            struct NodePair
            {
                TreeNode *Node;
                int Level;
                
                NodePair(TreeNode *N, int L)
                :
                Node(N),
                Level(L)
                {}
            };
            
            unordered_map<int,vector<int> > Temp;
            
            vector<vector<int> > Result;
            int Min = INT_MAX;
            int Max = INT_MIN;
            
            deque<NodePair> Q;
            
            if(root == NULL)
            {
                return (Result);
            }
            
            Q.push_back(NodePair(root,0));
            Q.push_back(NodePair(NULL,0));
            
            while(Q.empty() == false)
            {
                while(Q.front().Node != NULL)
                {
                    Temp[Q.front().Level].push_back(Q.front().Node->val);
                    Min = min(Min,Q.front().Level);
                    Max = max(Max,Q.front().Level);
                    
                    if(Q.front().Node->left)
                    {
                        Q.push_back(NodePair(Q.front().Node->left,Q.front().Level - 1));
                    }
                    
                    if(Q.front().Node->right)
                    {
                        Q.push_back(NodePair(Q.front().Node->right,Q.front().Level + 1));
                    }
                    
                    Q.pop_front();
                }
                
                Q.pop_front();
                
                if(Q.empty() == false)
                {
                    Q.push_back(NodePair(NULL,0));
                }
            }
            
            for(int i = Min; i <= Max; ++i)
            {
                Result.push_back(Temp[i]);
            }
            
            return (Result);
        }
    };

Log in to reply
 

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