In Tất Cả Nút Cách K Từ Nút Lá Trong C++

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

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

Nút lá của cây nhị phân là nút ở cuối cây.

Trong bài này, khoảng cách từ nút lá là nút ở mức cao hơn nút lá. Giả sử nút cách 2 từ nút lá ở mức 4 sẽ ở mức 2.

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

K = 2

Đầu ra – 6 9.

Để giải quyết, ta duyệt cây. Lưu tất cả tập nút cha (tổ tiên) mức theo mức cho đến khi đạt nút lá. In tổ tiên cách K từ nút lá. Đánh dấu nút đã thăm bằng mảng boolean để tránh trùng lặp.

Vì chỉ dùng duyệt cây nên độ phức tạp tỷ lệ với n. Độ phức tạp thời gian: O(n)

Ví Dụ

Chương trình minh họa logic:

#include <iostream>
using namespace std;
#define MAX_HEIGHT 10000

struct Node {
    int key;
    Node *left, *right;
};

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

void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k) {
    if (node == NULL) return;
    path[pathLen] = node->key;
    visited[pathLen] = false;
    pathLen++;
    if (node->left == NULL && node->right == NULL && pathLen - k - 1 >= 0 && visited[pathLen - k - 1] == false) {
        cout << path[pathLen - k - 1] << "\t";
        visited[pathLen - k - 1] = true;
        return;
    }
    nodesKatDistance(node->left, path, visited, pathLen, k);
    nodesKatDistance(node->right, path, visited, pathLen, k);
}

void printNodes(Node* node, int k) {
    int path[MAX_HEIGHT];
    bool visited[MAX_HEIGHT] = {false};
    nodesKatDistance(node, path, visited, 0, k);
}

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->left->left = insertNode(5);
    root->right->left->right = insertNode(1);
    int k = 2;
    cout << "Tất cả nút cách " << k << " từ nút lá là:\n";
    printNodes(root, k);
    return 0;
}

Đầu Ra

Tất cả nút cách 2 từ nút lá là:

6 9