Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหาผลรวมระดับสูงสุดในไบนารีทรีใน C ++


ในปัญหานี้ เราได้รับไบนารีทรีที่มีค่าบวกและลบ งานของเราคือ ค้นหาผลรวมระดับสูงสุดในไบนารีทรี

คำอธิบายปัญหา: เรามีไบนารีทรี เราจะหาผลรวมของทุกระดับในไบนารีทรี แล้วคืนค่าสูงสุดของมัน

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

ป้อนข้อมูล:

ค้นหาผลรวมระดับสูงสุดในไบนารีทรีใน C ++

ผลลัพธ์: 5

คำอธิบาย:

ผลรวมขององค์ประกอบที่ระดับ 1:3
ผลรวมขององค์ประกอบที่ระดับ 2:-3 + 4 =1
ผลรวมขององค์ประกอบที่ระดับ 3:5 - 1 + 6 - 5 =5

แนวทางการแก้ปัญหา

เพื่อแก้ปัญหา เราจำเป็นต้องสำรวจต้นไม้โดยใช้ระดับการข้ามผ่าน และสำหรับแต่ละระดับ เราจะหาผลรวมแล้วหาผลรวมระดับสูงสุด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

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

struct Node* newNode(int data){
   
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}

int findMaxLevelSum(struct Node* root){
   
   if (root == NULL)
      return 0;

   int maxSum = root->data;
   queue<Node*> q;
   q.push(root);
   while (!q.empty()){

      int count = q.size();
      int levelSum = 0;
      while (count--) {
         
         Node* temp = q.front();
         q.pop();
         levelSum = levelSum + temp->data;
         if (temp->left != NULL)
            q.push(temp->left);
         if (temp->right != NULL)
            q.push(temp->right);
      }
      maxSum = max(levelSum, maxSum);
   }
   return maxSum;
}

int main(){
   
   struct Node* root = newNode(3);
   root->left = newNode(-3);
   root->right = newNode(4);
   root->left->left = newNode(5);
   root->left->right = newNode(-1);
   root->right->left = newNode(6);
   root->right->right = newNode(-5);
   cout<<"The sum of level with maximum level sum is "<<findMaxLevelSum(root);
   return 0;
}

ผลลัพธ์

The sum of level with maximum level sum is 5