Pythonで葉ノードのリストから最小合計となる木を構築して合計値を求める方法

問題の概要

数値のリスト nums が与えられます。このリストは、ある二分木を中順走査（inorder traversal）した際の葉ノードを表しています。この木には次のようなルールがあります。

• すべての内部ノードは必ず2つの子を持ちます。
• 内部ノードの値は、「左部分木における最大の葉の値」と「右部分木における最大の葉の値」の積になります。

この条件のもとで、ノード値の合計が最小になるような木を構成し、その合計値を求めるのが目的です。

入出力の例

たとえば、入力が nums = [3, 5, 10] の場合、出力は 83 となります。最小の葉「3」に隣接する「5」を掛けて結合し、次に「5」に隣接する「10」を掛けていくことで、合計が最小になる木が得られます。

解法のアプローチ（貪欲法）

この問題は、貪欲法（グリーディー法）を使うことで効率的に解けます。基本的な考え方は、「常に最小の葉を取り除き、隣接する小さい方の葉との積を合計に加算していく」というものです。手順は以下の通りです。

• res := nums の全要素の合計値
• nums のサイズが 1 より大きい間、以下を繰り返す
  • i := nums の最小要素のインデックス
  • left := i > 0 の場合は nums[i - 1]、それ以外は無限大（∞）
  • right := i < nums のサイズ - 1 の場合は nums[i + 1]、それ以外は無限大（∞）
  • res := res + (left と right のうち小さい方) × nums[i] を加算し、nums から i 番目の要素を削除する
• 最終的な res を返す

端の要素の場合は片側しか隣接要素がないため、反対側を無限大として扱うことで、必ず存在する側の値が選ばれるようになっています。

サンプルコード（Python）

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
   def solve(self, nums):
      res = sum(nums)
      while len(nums) > 1:
         i = nums.index(min(nums))
         left = nums[i - 1] if i > 0 else float("inf")
         right = nums[i + 1] if i < len(nums) - 1 else float("inf")
         res += min(left, right) * nums.pop(i)

      return res

ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums))

入力

[3, 5, 10]

出力

83

処理の流れを追ってみる

初期状態の合計は 3 + 5 + 10 = 18 です。

• 1回目：最小値は「3」（インデックス0）。左は無限大、右は 5。合計に 5 × 3 = 15 を加算 → 33
• 2回目：残りは [5, 10]。最小値は「5」。左は無限大、右は 10。合計に 10 × 5 = 50 を加算 → 83

このように、時間計算量 O(n²)、空間計算量 O(n) で最小合計を求めることができます。