In tất cả các nút ở khoảng cách k từ một nút lá trong C ++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân và một số K. Chúng ta phải in ra tất cả các nút của cây cách nút lá là k.

Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút (một / hai / không có).

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

Trong bài toán 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 ở khoảng cách 2 so với nút lá ở cấp 4 sẽ ở cấp 2.

Hãy lấy một ví dụ để hiểu vấn đề

K =2

Đầu ra - 6 9.

Để giải quyết vấn đề này, chúng ta sẽ đi ngang qua cây. Tất cả lưu trữ tất cả các tập hợp nút cha (còn được gọi là nút tổ tiên) theo cấp độ mà nút lá sẽ đạt được. Bây giờ, chúng ta sẽ in tổ tiên ở khoảng cách k cách nút lá. Mặc dù việc đánh dấu duyệt các nút đã truy cập là rất quan trọng để tránh trùng lặp và chúng tôi sẽ sử dụng một mảng boolean cho mục đích này -

Vì mã chỉ sử dụng các đường ngang cây nên độ phức tạp tỷ lệ với n. Độ phức tạp về thời gian: O (n)

Ví dụ

Chương trình minh họa logic của chúng tôi -

#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<<"All nodes at distance "<<k<<" from leaf node are:\n";
   printNodes(root, k);
   return 0;
}

Đầu ra

Tất cả các nút ở khoảng cách 2 từ nút lá là -

6 9