In tất cả các nút trong cây nhị phân có K 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ố nguyên K và chúng ta phải in tất cả các nút của cây nhị phân có K lá trong cây con con của chúng.

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.

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

K =2

Đầu ra - {S}

Để giải quyết vấn đề này, chúng ta sẽ thực hiện chuyển ngang (postorder) cho cây. Bây giờ, chúng ta sẽ thấy từng cây con bên trái và cây con bên phải nếu tổng các lá là K, in ra nút hiện tại nếu không thì gọi đệ quy, số lượng lá của cây con.

Giải pháp này dựa trên việc đi ngang nên độ phức tạp sẽ theo thứ tự của kích thước của cây. Độ phức tạp về thời gian - O (n)

Ví dụ

Chương trình thực hiện phương pháp trên

#include<bits/stdc++.h>
using namespace std;
struct Node{
   char data ;
   struct Node * left, * right ;
};
struct Node * insertNode(char data){
   struct Node * node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int nodeWithKLeave(struct Node *ptr,int k){
   if (ptr == NULL)
      return 0;
   if (ptr->left == NULL && ptr->right == NULL)
      return 1;
   int total = nodeWithKLeave(ptr->left, k) + nodeWithKLeave(ptr->right, k);
   if (k == total)
      cout<<ptr->data<<" ";
   return total;
}
int main() {
   struct Node *root = insertNode('A');
   root->left = insertNode('B');
   root->right = insertNode('K');
   root->left->left = insertNode('N');
   root->left->right = insertNode('S');
   root->left->left->left = insertNode('X');
   root->left->left->right = insertNode('H');
   root->right->right = insertNode('E');
   root->right->left = insertNode('T');
   root->right->left->left = insertNode('O');
   root->right->left->right = insertNode('P');
   int K = 2;
   cout<<"Nodes with "<<K<<" leaves is :\n";
   nodeWithKLeave(root, K);
   return 0;
}

Đầu ra

Nodes with 2 leaves are:
N T