C++에서 이진 트리의 두 잎 사이의 최소 합 경로

문제 설명

각 노드 요소에 숫자가 포함된 이진 트리가 제공됩니다. 작업은 하나의 리프 노드에서 다른 리프 노드까지 가능한 최소 합계를 찾는 것입니다.

예시

위 트리에서 최소 하위 경로는 다음과 같이 -6입니다:(-4) + 3 + 2 + (-8) + 1

알고리즘

아이디어는 재귀 호출에서 두 개의 값을 유지하는 것입니다 -

• 현재 노드 아래에 있는 하위 트리의 최소 루트 대 리프 경로 합계
• 잎 사이의 최소 경로 합계
• 방문한 모든 노드 X에 대해 X의 왼쪽 및 오른쪽 하위 트리에서 최소 루트 대 리프 합을 찾아야 합니다. 그런 다음 두 값을 X의 데이터와 더하고 합을 현재 최소 경로 합과 비교합니다.

예시

#include <bits/stdc++.h>
using namespace std;
typedef struct node {
   int data;
   struct node *left;
   struct node *right;
} node;
node *newNode(int data) {
   node *n = new node;
   n->data = data;
   n->left = NULL;
   n->right = NULL;
   return n;
}
int getMinPath(node *root, int &result) {
   if (root == NULL) {
      return 0;
   }
   if (root->left == NULL && root->right == NULL) {
      return root->data;
   }
   int leftSum = getMinPath(root->left, result);
   int rightSum = getMinPath(root->right, result);
   if (root->left && root->right) {
      result = min(result, root->data + leftSum + rightSum);
      return min(root->data + leftSum, root->data + rightSum);
   }
   if (root->left == NULL) {
      return root->data + rightSum;
   } else {
      return root->data + leftSum;
   }
}
int getMinPath(node *root) {
   int result = INT_MAX;
   getMinPath(root, result);
   return result;
}
node *createTree() {
   node *root = newNode(2);
   root->left = newNode(3);
   root->right = newNode(-8);
   root->left->left = newNode(5);
   root->left->right = newNode(-4);
   root->right->left = newNode(1);
   root->right->right = newNode(10);
   return root;
}
int main() {
   node *root = createTree();
   cout << "Minimum sum path = " << getMinPath(root) << endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

출력

Minimum sum path = -6