Pythonの二分木でk長のパスを見つけるプログラム

一意の値を含む二分木があり、別の値kもあるとすると、ツリー内のkの長さの一意のパスの数を見つける必要があります。パスは、親から子へ、または子から親へのいずれかになります。一部のノードが一方のパスに表示され、もう一方のパスには表示されない場合、2つのパスは異なると見なされます。

したがって、入力が次のような場合

k =3の場合、パスは[12,8,3]、[12,8,10]、[8,12,15]、[3,8,10]であるため、出力は4になります。

これを解決するために、次の手順に従います-

• 関数dfs（）を定義します。これはノードを取ります

  • ノードがnullの場合、

    • 1とk-1の数が0のリストを返す

  • 左：=dfs（ノードの左側）

  • right：=dfs（ノードの右側）

  • 0からKの範囲のiの場合、実行

    • ans：=ans + left [i] * right [K-1 --i]

  • res：=0のサイズKのリスト

  • res [0]：=1、res [1]：=1

  • 1からK-1の範囲のiの場合、実行

    • res [i + 1]：=res [i + 1] + left [i]

    • res [i + 1]：=res [i + 1] + right [i]

  • 解像度を返す

• メインの方法から、次のようにします-

• ans：=0

• 
  

• dfs（root）

• 
  

• ansを返す

  
  

理解を深めるために、次の実装を見てみましょう-

例

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