Pythonで二分木における最も頻出する部分木の合計を求めるプログラム

問題の概要

二分木が与えられたとき、最も頻繁に出現する「部分木の合計値」を求めることを考えます。ここでいうノードの部分木合計とは、そのノード自身を含め、ノードより下にあるすべての値を足し合わせたものです。

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

この場合、出力は「3」になります。なぜなら、3は2回出現するからです。1回目は左の葉ノードの値として、もう1回は木全体の合計値 3 + 6 + (-6) = 3 として現れるためです。

解決のアプローチ

この問題を解くには、次の手順に従います。

• count := 空のマップ（辞書）を作成する
• 関数 getSum() を定義する。この関数はノードを引数として受け取る
• node が null の場合は 0 を返す
• mySum := getSum(ノードの左の子) + getSum(ノードの右の子) + ノードの値
• count[mySum] のカウントを1つ増やす
• mySum を返す
• メイン処理から getSum(root) を呼び出す

実装例

それでは、理解を深めるために実際のコードを見てみましょう。

from collections import defaultdict
class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.val = data
        self.left = left
        self.right = right
class Solution:
    def solve(self, root):
        count = defaultdict(int)
        def getSum(node):
            if not node:
                return 0
            mySum = getSum(node.left) + getSum(node.right) + node.val
            count[mySum] += 1
            return mySum
        getSum(root)
        return max(count, key=count.get)
ob = Solution()
root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)
print(ob.solve(root))

入力

root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)

出力

3

コードの解説

このコードでは、再帰的に各ノードの部分木合計を計算しています。getSum() 関数は、左右の子ノードの合計に自分自身の値を加えた結果を返しながら、その合計値の出現回数を defaultdict を使って記録していきます。最後に max(count, key=count.get) を呼び出すことで、出現回数が最も多い合計値を取得できます。

計算量について見てみると、木のすべてのノードを一度ずつ訪問するため時間計算量は O(n)、出現回数を記録するための辞書もノード数に依存するため、必要な記憶域も O(n) となります。