Pythonで二分木内の長さkの一意なパスを数えるプログラム

問題概要

一意な値を持つ二分木と整数 k が与えられます。このとき、木の中に存在する「長さ k の一意なパス」の総数を求めます。パスは親ノードから子ノードへ向かう方向でも、子ノードから親ノードへ向かう方向でも構いません。また、あるノードが片方のパスにのみ含まれる場合、その2つのパスは互いに異なるものとして扱います。

入力例と出力例

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

k = 3 の場合、出力は 4 になります。該当するパスは次の4本です。

• [12, 8, 3]
• [12, 8, 10]
• [8, 12, 15]
• [3, 8, 10]

解き方：深さ優先探索（DFS）によるアプローチ

この問題は、DFSで木を走査しながら、各ノードを基準とした距離ごとの経路数を集約していくことで解けます。具体的な手順は以下の通りです。

1. dfs() 関数を定義します。引数としてノードを受け取ります。
   • ノードが null の場合は、先頭に 1、続けて (K−1) 個の 0 を並べたリストを返します。
   • left := dfs(ノードの左の子)
   • right := dfs(ノードの右の子)
   • i を 0 から K−1 までループします。
     ans := ans + left[i] × right[K − 1 − i]
   • res := サイズ K のすべて 0 のリストを作成し、res[0] := 1、res[1] := 1 を設定します。
   • i を 1 から K−2 までループします。
     res[i + 1] := res[i + 1] + left[i]
     res[i + 1] := res[i + 1] + right[i]
   • res を返します。
2. メイン側では次の処理を行います。
   ans := 0 で初期化 → dfs(root) を呼び出す → ans を返す

ポイントとなるのは、各ノードで左右の部分木の情報を掛け合わせている箇所です。これにより、「そのノードを途中に含む長さ K のパス」の本数をすべて数え上げることができます。

Pythonでの実装例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, K):
      def dfs(node):
         if not node:
            return [1] + [0] * (K-1)
         left = dfs(node.left)
         right = dfs(node.right)
         for i in range(K):
            self.ans += left[i] * right[K - 1 - i]
         res = [0] * K
         res[0] = res[1] = 1
         for i in range(1, K - 1):
            res[i + 1] += left[i]
            res[i + 1] += right[i]
         return res
      self.ans = 0
      dfs(root)
      return self.ans
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 3))

入力

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
3

出力

4

計算量

各ノードを一度ずつ訪問し、訪問ごとに長さ K の配列操作を行うため、時間計算量は O(n × K) です。空間計算量は再帰スタックに依存し、木の高さを h とすると O(h)、木が偏っている場合は最悪で O(n) となります。