Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
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;
        }
    }
};

************************************************************/
#include <map>      //MYSOL WITH HNODE from AI
#include <queue>
#include <vector>

using namespace std;

void traverse(TreeNode<int>* root, int parh, map<TreeNode<int>*, int>& hord) { //get the horizontal distance array
    if (root) {
        hord[root] = parh;
        traverse(root->left, parh - 1, hord);
        traverse(root->right, parh + 1, hord);
    }
}

vector<int> verticalOrderTraversal(TreeNode<int>* root) {
    map<TreeNode<int>*, int> hord; //(node-horizontal distance)
    traverse(root, 0, hord);
    vector<int> ans;
    /* creating the map  of vector which will contain all nodes at 
    horizontal distance  */
    map<int, vector<int>> hnodes; 
    for (auto it = hord.begin(); it != hord.end(); it++) {
        hnodes[it->second].push_back(it->first->data);
    }
    // now hnodes has att the nodes mapped with horizontal distance (horizontal distance-node)
    
    for (auto it = hnodes.begin(); it != hnodes.end(); it++) {
        vector<int>& nodes = it->second;
        for (int node_val : nodes) {
            ans.push_back(node_val);
        }
    }

    return ans;
}