Pythonで二分木の全ノードの値の合計を求めるプログラム

二分木（バイナリツリー）にいくつかの値が格納されている場合、木に含まれるすべての値の合計を求めたいことがあります。

例えば、次のような二分木が入力として与えられたとします。

この場合、出力は 14 になります（2 + 4 + 3 + 5 = 14）。

解決のアプローチ

この問題を解くには、再帰を使って各ノードを順番に訪問し、値を足し合わせていきます。具体的な手順は以下の通りです。

• 関数 recurse() を定義します。引数としてノードを受け取ります。

• 変数 val に現在のノードの値を代入します。

• ノードの左の子が存在する場合は、val に左部分木の再帰結果を加算します。

• ノードの右の子が存在する場合は、val に右部分木の再帰結果を加算します。

• val を返します。

• メインの処理では以下を行います。

• ルートが存在しない（空の木である）場合は、0 を返します。

• それ以外の場合は、recurse(root) の結果を返します。

それでは、実際の実装を見てみましょう。

サンプルコード

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def recurse(self, node):
      val = node.val
      if node.left:
         val += self.recurse(node.left)
      if node.right:
         val += self.recurse(node.right)
      return val
   def solve(self, root):
      if not root:
         return 0
      return self.recurse(root)
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
print(ob.solve(root))

入力

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)

出力

14

コードの解説

このプログラムでは、まず TreeNode クラスで二分木の各ノードを表現しています。各ノードは値（val）と左右の子ノード（left、right）を持ちます。

Solution クラスの recurse() メソッドは、深さ優先探索（DFS）のように動作します。現在のノードの値から始めて、左側の部分木と右側の部分木を再帰的にたどりながら、すべてのノードの値を累積していきます。

時間計算量は O(n)（n はノードの総数）、空間計算量は最悪ケースで O(n)（木が偏っている場合）、バランスの取れた木なら O(log n) となります。