Giả sử chúng ta có một cây nhị phân chỉ chứa các chữ số từ 0-9, ở đây tất cả đường dẫn từ gốc đến lá có thể biểu thị một số.
Vì vậy, nếu cây giống -
Đây là đại diện cho hai đường dẫn 21 và 23, vì vậy đầu ra sẽ là 21 + 23 =44.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Tạo một hàm đệ quy được gọi là dfs (), hàm này sẽ có giá trị root và num. ban đầu num =0
- nếu nút không rỗng
- num:=num * 10 + giá trị của nút
- nếu nút bên phải không rỗng và nút bên trái không rỗng, thì '
- sum:=sum + num
- num:=num / 10
- trả về từ hàm
- dfs (bên phải của nút, num)
- dfs (bên trái của nút, num)
- num:=num / 10
- trả về từ phương thức
- tổng ban đầu:=0
- gọi dfs bằng root và
- trả về tổng.
Ví dụ (Python)
Hãy cùng chúng tôi xem cách 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