Pythonでバイナリツリーのルートからリーフまでの最長の合計パスの合計を見つけるプログラム

二分木があるとすると、ルートからリーフノードまでの最長パスの合計を見つける必要があります。同じ長いパスが2つある場合は、合計が大きいパスを返します。

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

その場合、出力は20になります。

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

• 関数rec（）を定義します。これには時間がかかります

• currがnullの場合、

  • return（0、0）

• 大きい：=rec（currの左側）の最大値、rec（currの右側）

• ペアを返します（bigger [0] + 1、bigger [1] + currの値）

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

• ret：=rec（root）

• retの1番目のインデックスを返す

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

例

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

出力

20