Python程序：查找二叉树路径形成的所有数字之和

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

因此，如果输入类似于

则输出将为 680，因为 46 (4 → 6)、432 (4 → 3 → 2)、435 (4 → 3 → 5)，它们的和为 913。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 solve()。它将接收根节点和一个字符串（初始为空字符串）。
  • 如果根节点存在且没有左子节点和右子节点，则
    • 返回将字符串与根节点的值连接起来后形成的整数。
  • 总和初始化为 0。
  • 如果根节点的左子节点不为空，则
    • 总和加上 solve(左子节点, 字符串连接根节点的值) 的数值。
  • 如果根节点的右子节点不为空，则
    • 总和加上 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

更新于: 2020-12-02

238 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告