Cho cây nhị phân và K, in nút thứ K trong duyệt dọc (vertical order). Nếu không có trả về -1. Ví dụ cây cho trước, duyệt dọc: 4 2 1 5 6 3 8 7 9, K=3 → 1.
Thực hiện duyệt dọc bằng hàng đợi và map theo độ ngang (hd). Sau đó duyệt map theo thứ tự khóa, đếm đến K.
Ví dụ
#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); }
Kết quả
Kth node in vertical traversal: 1