# 3 solutions, beats 98.9%, using DoubleLinkedList (Or hashmap\ vector), C++

• struct doubleList{
vector<int> val;
doubleList *left;
doubleList *right;
};
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {

vector<vector<int> > res;
if(!root)
return res;
doubleList *mid = new doubleList();
queue<pair<TreeNode *,doubleList *> > Q;
Q.push({root,mid});
doubleList *leftbound = mid;
while(!Q.empty())
{
auto node = Q.front();
Q.pop();
node.second->val.push_back(node.first->val);
if(node.first->left)
{
if(node.second->left==NULL)
{
node.second->left = new doubleList();
node.second->left->right = node.second;
leftbound = node.second->left;
}
Q.push({node.first->left,node.second->left});
}
if(node.first->right)
{
if(node.second->right==NULL)
{
node.second->right = new doubleList();
node.second->right->left = node.second;
}
Q.push({node.first->right,node.second->right});
}
}
while(leftbound)
{
res.push_back(leftbound->val);
leftbound = leftbound->right;
}
return res;

// // ------Two vectors-----
// vector<vector<int>> res;
// if(!root)
//     return res;
// vector<vector<int>>left;
// vector<vector<int>> right;
// vector<int> mid;
// queue<pair<TreeNode *,int> > Q;
// Q.push({root,0});
// while(!Q.empty())
// {
//     auto node = Q.front();
//     Q.pop();
//     if(node.second == 0)
//         mid.push_back(node.first->val);
//     else if(node.second>0)
//     {
//         if(node.second > right.size())
//         {
//             right.push_back({node.first->val});
//         }
//         else
//             right[node.second-1].push_back(node.first->val);
//     }
//     else if(node.second<0)
//     {
//         if(-node.second > left.size())
//         {
//             left.push_back({node.first->val});
//         }
//         else
//             left[-node.second-1].push_back(node.first->val);
//     }
//     if(node.first->left) Q.push({node.first->left,node.second-1});
//     if(node.first->right) Q.push({node.first->right,node.second+1});
// }
// reverse(left.begin(),left.end());
// left.push_back(mid);
// for(auto it:right)
// left.push_back(it);
// return left;

// ------HashMap----

// unordered_map<int, vector<int>> vertical;
// vector<vector<int> > res;
// if(!root)
//     return res;
// queue<pair<TreeNode *, int> > Q;
// Q.push({root,0});
// int minindex = 0,maxindex = 0;
// while(!Q.empty())
// {
//     auto node = Q.front();
//     Q.pop();
//     vertical[node.second].push_back(node.first->val);
//     minindex = min(node.second,minindex);
//     maxindex = max(node.second,maxindex);
//     if(node.first->left) Q.push({node.first->left,node.second-1});
//     if(node.first->right) Q.push({node.first->right,node.second+1});
// }
// for(int i = minindex;i<=maxindex;i++)
// res.push_back(vertical[i]);
// return res;

}
};

1. Nice solution!