C++の二分木の2つのリーフ間の最小合計パス

問題の説明

各ノード要素に数値が含まれている二分木があるとします。タスクは、あるリーフノードから別のリーフノードへの可能な最小の合計を見つけることです。

例

上記のツリーでは、最小サブパスは次のように-6です：（-4）+ 3 + 2 +（-8）+ 1

アルゴリズム

アイデアは、再帰呼び出しで2つの値を維持することです-

• 現在のノードの下にルート化されたサブツリーのルートからリーフへの最小パスの合計
• 葉の間の最小経路合計
• 訪問したノードXごとに、Xの左右のサブツリーでルートからリーフへの最小の合計を見つける必要があります。次に、2つの値を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