Untitled
plain_text
a month ago
1.5 kB
0
Indexable
Never
/************************************************************ Following is the TreeNode class structure: template <typename T> class TreeNode { public: T data; TreeNode<T> *left; TreeNode<T> *right; TreeNode(T dat) { this->data = dat; left = NULL; right = NULL; } }; ************************************************************/ #include<map> #include<queue> #include<vector> /* first input of every horizontal distance array will be top node */ vector<int> getTopView(TreeNode<int> *root) { vector<int> ans; if(root==NULL) return ans; map<int,int> topnode; //(distance,topnode) //vector wont work for topnode queue<pair<TreeNode<int>*,int>> q; // (node,horizontal dsit) q.push(make_pair(root,0)); while(!q.empty()){ pair<TreeNode<int>*,int> front=q.front(); //getting the node q.pop(); //pop korte keno BHULE jasss??? TreeNode<int>* tmp=front.first; int dist=front.second; if(topnode.find(dist)==topnode.end()){ //checking if its the first topnode[dist]=tmp->data; } if(tmp->left) q.push(make_pair(tmp->left,dist-1)); if(tmp->right) q.push(make_pair(tmp->right,dist+1)); } //now topnode has all topnodes in format (distance,node) for(auto i:topnode){ ans.push_back(i.second); } return ans; }