Chương trình cập nhật giá trị nút cây nhị phân bằng tổng cây con trái và phải trong Python

Cho một cây nhị phân, cập nhật giá trị mỗi nút bằng tổng giá trị của chính nó cộng với tổng tất cả các nút trong cây con trái và cây con phải.

Ví dụ

Cây đầu vào: (hình ảnh minh họa).
Cây sau khi cập nhật: (hình ảnh minh họa).

Thuật toán

1. Định nghĩa hàm đệ quy tree_sum(root):
   • Nếu root là None, trả về 0.
   • Cập nhật root.data = tree_sum(root.left) + tree_sum(root.right) + root.data.
   • Trả về root.data.
2. Gọi tree_sum(root) từ phương thức chính.
3. Trả về root.

Mã nguồn Python

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=', ')
        inorder(root.right)

class Solution:
    def solve(self, root):
        def tree_sum(root):
            if root is None:
                return 0
            root.data = tree_sum(root.left) + tree_sum(root.right) + root.data
            return root.data
        tree_sum(root)
        return root

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(9)
root.left.right = TreeNode(7)
ob.solve(root)
inorder(root)

Đầu vào / Đầu ra

Input: root = TreeNode(12) ...
Output: 9, 19, 7, 25, 4,