C++에서 허용되지 않는 인접 레벨이 있는 트리의 최대 합계

이 문제에서는 양수로 구성된 이진 트리가 제공됩니다. 우리의 임무는 C++에서 허용되지 않는 인접 레벨을 가진 트리에서 최대 합을 찾는 프로그램을 만드는 것입니다.

코드 설명

여기에서 트리의 인접한 두 수준의 노드가 합계에 포함되지 않는 방식으로 트리 노드의 최대 합계를 찾습니다.

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

출력

21

설명

루트를 시작 레벨로 사용, 합계 =5 + 3 + 8 + 1 =17 루트의 하위 자식을 시작 레벨로 취, 합계 =2 + 6 + 9 + 4 =21

솔루션 접근 방식

maxSum을 찾기 위한 한 가지 조건은 인접 요소가 없다는 것입니다. 이를 위해 루트 노드(레벨 1)에서 하나의 합계 세트를 가져오고 자식 노드(레벨 2)에서 다른 합계를 가져옵니다. 손자 노드를 찾아 현재 노드에서 다음 합 노드를 추출합니다.

이를 위해 재귀적으로 maxSum 값을 찾은 다음 레벨 1 또는 레벨 2에서 시작하는 합계의 최대 합계 값이 결과 maxSum이 됩니다.

예시

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

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node* left, *right;
   Node(int item){
      data = item;
   }
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
   if (root == NULL)
      return 0;
      int sum = root->data;
   if (root->left != NULL){
      sum += getMaxSum(root->left->left);
      sum += getMaxSum(root->left->right);
   }
   if (root->right != NULL){
      sum += getMaxSum(root->right->left);
      sum += getMaxSum(root->right->right);
   }
   return sum;
}
int getMaxSum(Node* root){
   if (root == NULL)
      return 0;
      return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
   Node* root = new Node(5);
   root->left = new Node(2);
   root->right = new Node(10);
   root->left->left = new Node(4);
   root->left->right = new Node(6);
   root->right->right = new Node(9);
   cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
   return 0;
}

출력

The maximum sum from a tree with adjacent levels not allowed is 24