หาโหนดที่ k ในการท่องแบบแนวตั้งของต้นไม้ไบนารีใน C++

สมมติว่ามีต้นไม้ไบนารีและค่า K งานคือพิมพ์โหนดที่ K ในการท่องแบบแนวตั้ง (Vertical Order Traversal) หากไม่มีโหนดดังกล่าว ให้คืนค่า -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