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