在 Python 中找到二叉树路径中所有数字的和

假设我们有一棵二叉树，每个节点都包含来自0到9的一个数字。现在，从根到叶子的每条路径都表示一个数字及其数字的顺序。我们必须找到树中表示的所有路径的数字的和。

因此，如果输入如下所示：

那么输出将为680，因为46（4→6），432（4→3→2），435（4→3→5），它们的和为913。

要解决此问题，我们将遵循以下步骤：

• 定义solve()函数。这将取root 和 string:=空字符串
• 如果root不为零且root.left和root.right都为零，则
  • 返回int(string+ str(root)的值)
• total:= 0
• 如果root的左边不为空，则
  • total := total + parse string concatenate root的数值的解决方法(根左边)
• 如果root的右边不为空，则
  • total := total + 解决右边root parse string concatatenate root的值的数值
• 返回total

让我们看一下以下实现，以便更好地理解：

示例

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