C++のバイナリツリーの最大パス合計

この問題を解決するために、ツリートラバーサルを実行し、現在のノードの左側のサブツリー/右側のサブツリーの最大合計を格納します。また、これまでのところ、2つのリーフノード間の最大パスが見つかります。

の場合、すべてのノードで、そのサブツリーの可能な最大のリーフからリーフへのパスが見つかります。次に、それを全体の最大パスと比較し、両方の値の最大値をグローバル最大パス合計値に格納します。

ソリューションをよりよく理解するために、この例からこのソリューションを見てみましょう-

グローバル最大合計=6（パス2→5→-1の場合）

次に、ルートノードとして6を取得することを確認します。

左側のサブツリー-

リーフノードまでのパスの合計は7と4です。

最大は7です（パス5→2の場合）。

右側のサブツリー-

リーフノードまでのパスの合計は、パス（1rarr; -3rarr; 7）に対して5であり、これは1つの可能な方法です。

いいえ、リーフノード間のパスの合計は-

左側のサブツリーのリーフからルート（6）までの最大合計+ルート+右側のサブツリーのリーフからルート（6）までの最大合計=7 + 6 + 5 =18

グローバル最大パス合計（6）と比較すると、新しいグローバル最大パス合計=18です。

例

2つのリーフノード間の最大パス合計を見つけるプログラム-

#include <bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   struct Node* left, *right;
};
struct Node* insertNode(int data){
   struct Node* node = new(struct Node);
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
   if (root==NULL) return 0;
   if (!root->left && !root->right) return root->data;
   int leftSubTree = maxPathSumLeaf(root->left, maxSum);
   int rightSubTree = maxPathSumLeaf(root->right, maxSum);
   if (root->left && root->right){
      maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
      return max(leftSubTree, rightSubTree) + root->data;
   }
   return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
   struct Node *root = insertNode(-2);
   root->left = insertNode(6);
   root->right = insertNode(4);
   root->left->left = insertNode(5);
   root->left->right = insertNode(1);
   root->left->left->left = insertNode(2);
   root->left->left->right = insertNode(-1);
   root->left->right->left = insertNode(-3);
   root->left->right->left->left = insertNode(7);
   root->right->left = insertNode(9);
   root->right->right = insertNode(3);
   int maxSum = INT_MIN;
   maxPathSumLeaf(root, maxSum);
   cout<<"Max pathSum of between two leaf nodes for the given binary tree is "<<maxSum;
   return 0;
}

出力

Max pathSum of between two leaf nodes for the given binary tree is 24