พิมพ์โหนดทั้งหมดในไบนารีทรีที่มี K ออกจาก C++

ในปัญหานี้ เราได้รับไบนารีทรีและจำนวนเต็ม K และเราต้องพิมพ์โหนดทั้งหมดของไบนารีทรีที่มี K ออกจากทรีย่อยย่อย

ต้นไม้ไบนารี เป็นต้นไม้พิเศษที่แต่ละโหนดมีโหนดสูงสุดสองโหนด (หนึ่ง/สอง/ไม่มี)

โหนดลีฟ ของไบนารีทรีคือโหนดที่ส่วนท้ายของทรี

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −

K =2

ผลลัพธ์ − {ส}

เพื่อแก้ปัญหานี้ เราจะทำการข้าม (postorder) สำหรับต้นไม้ ตอนนี้ เราจะเห็นแต่ละทรีย่อยทางซ้ายและทรีย่อยทางขวา ถ้าผลรวมของใบไม้เป็น K ให้พิมพ์ โหนดปัจจุบัน มิฉะนั้นจะเรียกซ้ำ, การนับใบของต้นไม้ย่อย

วิธีแก้ปัญหานี้อิงตามการสำรวจ ดังนั้นความซับซ้อนจะอยู่ที่ลำดับของขนาดของต้นไม้ ความซับซ้อนของเวลา − O(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;
}

ผลลัพธ์

Nodes with 2 leaves are:
N T