Chương trình tìm tổng tất cả các phần tử của cây bằng Python

Giả sử chúng ta có một cây nhị phân chứa một số giá trị, chúng ta phải tìm tổng của tất cả các giá trị trong cây.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 14

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm recurse (). Điều này sẽ lấy nút

• val:=giá trị của nút

• nếu bên trái của nút không rỗng, thì

  • val:=val + recurse (bên trái của nút)

• nếu bên phải của nút không phải là-null, thì

  • val:=val + recurse (bên phải của nút)

• trả lại giá trị

• Từ phương thức chính, thực hiện như sau -

• nếu không gốc là khác 0, thì

  • trả về 0

• trả về đệ quy (gốc)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

14