Tổng các số từ gốc đến lá trong Python

Cho một cây nhị phân chứa các chữ số 0-9, mỗi đường đi từ gốc đến lá đại diện cho một số.

Ví dụ cây như sau:

Đại diện cho hai đường đi 21 và 23, nên đầu ra là 21 + 23 = 44.

Giải pháp dùng DFS đệ quy:

• Tạo hàm dfs() nhận node và num (khởi tạo num = 0)
• Nếu node không null:
  • num := num * 10 + giá trị node
  • Nếu node không có con trái và con phải (là lá):
    • sum := sum + num
    • num := num / 10
    • Trả về
  • dfs(node.right, num)
  • dfs(node.left, num)
  • num := num / 10
  • Trả về
• Khởi tạo sum := 0
• Gọi dfs(root, 0)
• Trả về sum

Ví dụ (Python):

Xem triển khai sau để hiểu rõ hơn:

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

def insert(temp, data): 
    que = [] 
    que.append(temp) 
    while len(que): 
        temp = que[0] 
        que.pop(0) 
        if not temp.left: 
            if data is not None: 
                temp.left = TreeNode(data) 
            else: 
                temp.left = TreeNode(0) 
            break 
        else: 
            que.append(temp.left) 
        if not temp.right: 
            if data is not None: 
                temp.right = TreeNode(data) 
            else: 
                temp.right = TreeNode(0) 
            break 
        else: 
            que.append(temp.right) 

def make_tree(elements): 
    Tree = TreeNode(elements[0]) 
    for element in elements[1:]: 
        insert(Tree, element) 
    return Tree 

class Solution(object): 
    def sumNumbers(self, root): 
        self.sum = 0 
        self.dfs(root) 
        return self.sum 
    
    def dfs(self, node, num=0): 
        if node: 
            num = num * 10 + node.data 
            if not node.right and not node.left: 
                self.sum += num 
                num /= 10 
                return 
            self.dfs(node.right, num) 
            self.dfs(node.left, num) 
            num /= 10 
        return 

ob1 = Solution() 
tree = make_tree([2,1,3]) 
print(ob1.sumNumbers(tree))

Đầu vào

[2,1,3]

Đầu ra

44