Chương trình tìm tổng của tất cả các số được tạo bằng đường dẫn của cây nhị phân trong python

Giả sử chúng ta có một cây nhị phân trong đó mỗi nút chứa một chữ số duy nhất từ ​​0 đến 9. Bây giờ mỗi đường dẫn từ gốc đến lá biểu diễn một số với các chữ số của nó theo thứ tự. Chúng ta phải tìm tổng các số được biểu thị bằng tất cả các đường dẫn trong cây.

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

thì đầu ra sẽ là 680 là 46 (4 → 6), 432 (4 → 3 → 2), 435 (4 → 3 → 5) và tổng của chúng là 913.

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

• Xác định một hàm giải quyết (). Điều này sẽ bắt nguồn từ root, string:=blank string
• nếu root và không root.left và không root.right là khác 0, thì
  • trả về int (chuỗi + str (giá trị của gốc))
• tổng số:=0
• nếu bên trái của thư mục gốc không rỗng, thì
  • total:=tổng + giá trị số của giải (bên trái của gốc, giá trị nối chuỗi của gốc)
• nếu quyền của thư mục gốc không rỗng, thì
  • total:=tổng + giá trị số của giải (bên phải của gốc, giá trị nối chuỗi của gốc)
• tổng trả lại

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

Đầu vào

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

Đầu ra

913