Chương trình tìm tổng tất cả các phần tử của một cây trong 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í dụ, nếu đầu vào như hình:

thì đầu ra sẽ là 14

Để giải quyết, chúng ta thực hiện các bước sau:

• Định nghĩa hàm recurse(). Hàm này nhận node
• val := giá trị của node
• nếu left của node không null, val := val + recurse(left của node)
• nếu right của node không null, val := val + recurse(right của node)
• trả về val
• Từ phương thức chính:
  • nếu root không tồn tại, trả về 0
  • trả về recurse(root)

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

Input

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

Output

14