Tổng tối đa từ một cây có các cấp liền kề không được phép trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân bao gồm các số dương. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Tổng tối đa từ một cây có các mức liền kề không được phép trong C ++.

Mô tả mã

Ở đây, chúng ta sẽ tìm tổng số nút lớn nhất của cây theo cách mà tổng không chứa các nút từ hai cấp độ liền kề của cây.

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

Đầu ra

21

Giải thích

Lấy gốc làm mức bắt đầu, sum =5 + 3 + 8 + 1 =17 Lấy con của gốc làm mức bắt đầu, sum =2 + 6 + 9 + 4 =21

Phương pháp tiếp cận giải pháp

Để tìm maxSum, một điều kiện là không có phần tử liền kề. Đối với điều này, chúng tôi sẽ lấy một tập hợp tổng từ nút gốc (Mức 1) và một bộ khác từ nút con (Mức 2). Các nút tổng tiếp theo sẽ được trích xuất từ ​​nút hiện tại bằng cách tìm các nút cháu.

Đối với điều này, chúng tôi sẽ tìm một cách đệ quy giá trị maxSum và sau đó giá trị tổng lớn nhất cho tổng bắt đầu từ cấp 1 hoặc cấp 2 sẽ là maxSum kết quả.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node* left, *right;
   Node(int item){
      data = item;
   }
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
   if (root == NULL)
      return 0;
      int sum = root->data;
   if (root->left != NULL){
      sum += getMaxSum(root->left->left);
      sum += getMaxSum(root->left->right);
   }
   if (root->right != NULL){
      sum += getMaxSum(root->right->left);
      sum += getMaxSum(root->right->right);
   }
   return sum;
}
int getMaxSum(Node* root){
   if (root == NULL)
      return 0;
      return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
   Node* root = new Node(5);
   root->left = new Node(2);
   root->right = new Node(10);
   root->left->left = new Node(4);
   root->left->right = new Node(6);
   root->right->right = new Node(9);
   cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
   return 0;
}

Đầu ra

The maximum sum from a tree with adjacent levels not allowed is 24