In Tất Cả Nút Cách K Từ Nút Cho Trước Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân, một nút mục tiêu và một số nguyên K. In tất cả các nút của cây ở khoảng cách K từ nút mục tiêu.

Cây nhị phân là cây đặc biệt mà mỗi nút có tối đa 2 nút con.

Ví dụ để hiểu vấn đề:

K = 2

Nút mục tiêu: 9

Đầu ra:

5 1 3

Giải thích – Khoảng cách có thể lên cha, xuống con, hoặc cùng cấp. Trả về các nút tương ứng.

Để giải quyết, ta hiểu các loại nút cách K từ nút mục tiêu. Từ ví dụ, nút cách K có thể ở cây con của nút mục tiêu (5 và 1) hoặc ở cây con của tổ tiên của nút mục tiêu (3).

Trường hợp 1: Duyệt cây con của nút mục tiêu, kiểm tra khoảng cách từ nút mục tiêu là K. Nếu có in nút.

Trường hợp 2: Kiểm tra các tổ tiên và cây con của tổ tiên cho nút mục tiêu, in tất cả nút cách K.

Ví Dụ

Chương trình minh họa giải pháp:

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *left, *right;
};

void printSubtreeNodes(node* root, int k) {
    if (root == NULL || k < 0) return;
    if (k == 0) {
        cout << root->data << "\t";
        return;
    }
    printSubtreeNodes(root->left, k - 1);
    printSubtreeNodes(root->right, k - 1);
}

int printKNodes(node* root, node* target, int k) {
    if (root == NULL) return -1;
    if (root == target) {
        printSubtreeNodes(root, k);
        return 0;
    }
    int dl = printKNodes(root->left, target, k);
    if (dl != -1) {
        if (dl + 1 == k)
            cout << root->data << "\t";
        else
            printSubtreeNodes(root->right, k - dl - 2);
        return 1 + dl;
    }
    int dr = printKNodes(root->right, target, k);
    if (dr != -1) {
        if (dr + 1 == k)
            cout << root->data << endl;
        else
            printSubtreeNodes(root->left, k - dr - 2);
        return 1 + dr;
    }
    return -1;
}

node* insertNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->right = insertNode(4);
    root->right->left = insertNode(8);
    root->right->right = insertNode(10);
    root->right->right->left = insertNode(5);
    root->right->right->right = insertNode(1);
    node* target = root->right;
    int K = 2;
    cout << "Các nút cách " << K << " từ nút mục tiêu là:\n";
    printKNodes(root, target, K);
    return 0;
}

Đầu Ra

Các nút cách 2 từ nút mục tiêu là: 5 1 3