Untitled
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; }