Tìm tổng cây con lớn nhất trong một cây trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là tìm tổng cây con lớn nhất trong một cây.

Mô tả sự cố: Cây nhị phân bao gồm các giá trị dương và âm. Và chúng ta cần tìm cây con có tổng số nút lớn nhất.

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

Đầu ra: 13

Giải thích:

Tổng của cây con bên trái là 7
Tổng của cây con bên phải là 1
Tổng của cây là 13

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

Để giải quyết vấn đề, chúng tôi sẽ thực hiện duyệt sau đơn hàng. Tính tổng các nút của cây con bên trái và cây con bên phải. Đối với nút hiện tại, hãy kiểm tra xem tổng các nút của nút hiện tại có lớn hơn tổng của cây con bên trái hoặc bên phải hay không. Đối với mỗi nút từ lá đến gốc, hãy tìm tổng lớn nhất.

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

Ví dụ

#include <iostream>
using namespace std;

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

Node* newNode(int key) {
   
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}

int calcSumTreeSumRec(Node* root, int&amp; ans) {
   
   if (root == NULL)  
      return 0;
   int currSum = root->key + calcSumTreeSumRec(root->left, ans)+ calcSumTreeSumRec(root->right, ans);
   ans = max(ans, currSum);

   return currSum;
}

int calcMaxSubTreeSum(Node* root)
{
   if (root == NULL)  
      return 0;
   int ans = -100;
   calcSumTreeSumRec(root, ans);
   return ans;
}

int main() {

   Node* root = newNode(5);
   root->left = newNode(-4);
   root->right = newNode(4);
   root->left->left = newNode(3);
   root->left->right = newNode(8);
   root->right->left = newNode(-5);
   root->right->right = newNode(2);

   cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
   return 0;
}

Đầu ra

The largest subtree sum is 13