Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
8
Indexable
Never
#include <bits/stdc++.h> 
/************************************************************

Following is the Binary Tree node class
    
template <typename T = int>
class TreeNode
{
public:
    T data;
    TreeNode<T> *left;
    TreeNode<T> *right;

    TreeNode(T val)
    {
        this->data = val;
        left = NULL;
        right = NULL;
    }

    ~TreeNode()
    {
        if (left != NULL)
        {
            delete left;
        }
        if (right != NULL)
        {
            delete right;
        }
    }
};

************************************************************/

vector<int> verticalOrderTraversal(TreeNode<int> *root)
{
    // get the map init
    map<int,map<int,multiset<int>>> mapper;
    // get the queue inti
    queue<pair<TreeNode<int> *,pair<int,int>>> que;
    // push first elem to queue
    que.push({root,{0,0}});
    // while loop 
    // queue helps in easy iteration through the tree
    while(!que.empty()){
        // give me first element 
        auto elem = que.front();
        //  then remove it
        que.pop();
        
        TreeNode<int>* node = elem.first;

        //  push this to map!

        mapper[elem.second.first][elem.second.second].insert(node->data);

        if(node->left != NULL){
            // call my left
            que.push({node->left,{elem.second.first-1,elem.second.second +1}});
        }
        if(node->right != NULL){
            // call my rgiht
            que.push({node->right,{elem.second.first+1,elem.second.second +1}});
        }
    }


    // push answer from map to vector 
    vector<int> answer;
    for(auto it:mapper){
        for(auto it2:it.second){
            answer.insert(answer.end(), it2.second.begin(), it2.second.end());
        }
    }
    // return vector
    return answer;
}