C++의 트리에서 가장 큰 하위 트리 합계 찾기

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 트리에서 가장 큰 하위 트리 합을 찾는 것입니다.

문제 설명: 이진 트리는 양수 값과 음수 값으로 구성됩니다. 그리고 노드의 합이 최대인 하위 트리를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

<강한>

출력: 13

설명:

왼쪽 하위 트리의 합은 7입니다.
오른쪽 하위 트리의 합은 1입니다.
트리의 합은 13입니다.

솔루션 접근 방식

문제를 해결하기 위해 후위 순회를 수행합니다. 노드 왼쪽 하위 트리와 오른쪽 하위 트리의 합을 계산합니다. 현재 노드의 경우 현재 노드의 노드 합이 왼쪽 또는 오른쪽 하위 트리의 합보다 큰지 확인합니다. 리프에서 루트까지의 각 노드에 대해 최대 합계를 찾습니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#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;
}

출력

The largest subtree sum is 13