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

Arnab Chakraborty

更新於: 2020-12-02

238 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始