Pythonの二分木のパスによって形成されたすべての数の合計を見つけるプログラム

各ノードに0から9までの1桁の数字が含まれている二分木があるとします。ここで、ルートからリーフまでの各パスは、数字が順番に並んだ数字を表します。ツリー内のすべてのパスで表される数値の合計を見つける必要があります。

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

その場合、出力は680（46（4→6）、432（4→3→2）、435（4→3→5））になり、それらの合計は913になります。

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

• 関数solve（）を定義します。これはルートを取ります、string：=空白の文字列
• root.leftではなくroot.rightではなくrootがゼロ以外の場合、
  • return int（string + str（value of root））
• 合計：=0
• ルートの左側がnullでない場合、
  • total：=total +solveの数値（ルートの左側、ルートの文字列連結値）
• ルートの権利がnullでない場合、
  • total：=total +solveの数値（ルートの右、ルートの文字列連結値）
• 合計を返す

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

例

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, string=""):
      if root and not root.left and not root.right:
         return int(string + str(root.val))

      total = 0
      if root.left:
         total += int(self.solve(root.left, string + str(root.val)))

      if root.right:
         total += int(self.solve(root.right, string + str(root.val)))

      return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

入力

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

出力

913