Python程式：查詢樹中所有元素的和

假設我們有一個包含一些值的二叉樹，我們需要找到樹中所有值的總和。

因此，如果輸入類似於

則輸出將為 14

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 recurse()。它將接收節點作為引數。

  • val := 節點的值

  • 如果節點的左子節點不為空，則

    • val := val + recurse(節點的左子節點)

  • 如果節點的右子節點不為空，則

    • val := val + recurse(節點的右子節點)

  • 返回 val

  • 從主方法中執行以下操作：

  • 如果根節點不為零，則

    • 返回 0

  • 返回 recurse(根節點)

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def recurse(self, node):
      val = node.val
      if node.left:
         val += self.recurse(node.left)
      if node.right:
         val += self.recurse(node.right)
      return val
   def solve(self, root):
      if not root:
         return 0
      return self.recurse(root)
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
print(ob.solve(root))

輸入

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

輸出

14

更新於: 2020年10月21日

808 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告