C++에서 이진 트리의 수직 순서 순회에서 k 번째 노드 찾기

이진 트리와 값 K가 있다고 가정합니다. 작업은 수직 순서 순회에서 K 번째 노드를 인쇄하는 것입니다. 그러한 노드가 없으면 -1을 반환합니다. 트리가 아래와 같다면 -

수직 순서 순회는 −

4
2
1 5 6
3 8
7
9

따라서 K =3이면 결과는 1이 됩니다.

접근 방식은 간단합니다. 수직 순서 순회를 수행한 다음 현재 노드가 k번째 노드인지 확인한 다음 반환합니다.

예시

#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
class Node {
   public:
   int key;
   Node *left, *right;
};
Node* getNode(int key){
   Node* node = new Node;
   node->key = key;
   node->left = node->right = NULL;
   return node;
}
int findKthNodeVertical(Node* root, int k) {
   if (!root || k == 0)
      return -1;
   int n = 0;
   int k_node = -1;
   map<int, vector<int> > current_map;
   int hd = 0;
   queue<pair<Node*, int> > que;
   que.push(make_pair(root, hd));
   while (!que.empty()) {
      pair<Node*, int> temp = que.front();
      que.pop();
      hd = temp.second;
      Node* node = temp.first;
      current_map[hd].push_back(node->key);
      if (node->left != NULL)
         que.push(make_pair(node->left, hd - 1));
      if (node->right != NULL)
      que.push(make_pair(node->right, hd + 1));
   }
   map<int, vector<int> >::iterator it;
   for (it = current_map.begin(); it != current_map.end(); it++) {
      for (int i = 0; i < it->second.size(); ++i) {
         n++;
         if (n == k)
            return (it->second[i]);
      }
   }
   if (k_node == -1)
      return -1;
}
int main() {
   Node* root = getNode(1);
   root->left = getNode(2);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(5);
   root->right->left = getNode(6);
   root->right->right = getNode(7);
   root->right->left->right = getNode(8);
   root->right->right->right = getNode(9);
   int k = 3;
   cout << "Kth node in vertical traversal: " << findKthNodeVertical(root, k);
}

출력

Kth node in vertical traversal: 1