이 문제에서는 값을 포함하는 각 노드가 있는 이진 트리가 제공됩니다. 우리의 임무는 이진 트리의 두 잎 사이의 최대 경로 합을 찾는 프로그램을 만드는 것입니다.
여기서 우리는 값의 최대 합을 제공할 하나의 리프 노드에서 다른 리프 노드까지의 경로를 찾아야 합니다. 이 최대 합 경로는 루트 노드를 포함할 수 있거나 포함할 수 없습니다.
이진 트리 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리 데이터 구조입니다. 이를 왼쪽 자식과 오른쪽 자식이라고 합니다.
예 -
문제를 이해하기 위해 예를 들어 보겠습니다. −
입력 - //이진 트리...
출력 − 24
설명 − 리프 노드 − 2에서 9까지의 경로는 (2 + 5 + 6 -2 + 4 + 9 ) =24인 최대 합을 제공합니다.
이 문제를 해결하기 위해 트리 순회를 수행하고 현재 노드에 대한 왼쪽 하위 트리/오른쪽 하위 트리의 최대 합계를 저장합니다. 또한 지금까지 두 리프 노드 사이의 최대 경로를 찾습니다.
모든 노드에 대해 하위 트리에 대해 가능한 최대 리프 간 경로를 찾을 수 있습니다. 그런 다음 전체 최대 경로와 비교하여 두 값의 최대값을 전역 최대 경로 합계 값에 저장합니다.
솔루션을 더 잘 이해하기 위해 예제에서 이 솔루션을 살펴보겠습니다. −
전역 최대 합계 =6(경로 2→5→-1의 경우)
이제 6을 루트 노드로 사용하는지 확인합니다.
왼쪽 하위 트리에서 -
리프 노드까지의 경로의 합은 7과 4입니다.
최대값은 7입니다(경로 5→2의 경우).
오른쪽 하위 트리에서 -
리프 노드까지의 경로 합은 경로(1rarr;-3rarr;7)에 대해 5이며 가능한 한 방법입니다.
아니요, 리프 노드 간의 경로 합은 -
입니다.왼쪽 하위 트리에서 리프에서 루트(6)까지의 최대 합계 + 루트 + 오른쪽 하위 트리에서 리프에서 루트(6)까지의 최대 합계 =7 + 6 + 5 =18.
전역 최대 경로 합계(6)와 비교하면 새로운 전역 최대 경로 합계 =18입니다.
예시
두 리프 노드 사이의 최대 경로 합을 찾는 프로그램 -
#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