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


  • 8
    S
    struct doubleList{
        vector<int> val;
        doubleList *left;
        doubleList *right;
    };
    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            //Double Linked List. Fastest
    
            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;
            
        }
    };

  • 0
    H
    1. Nice solution!

  • 0
    D

    could you please explain the double linked list solution ?


  • 0
    J

    really awesome


Log in to reply
 

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