สมมติว่าเรามีไบนารีทรีที่มีตัวเลขตั้งแต่ 0-9 เท่านั้น เส้นทางจากรากถึงใบทั้งหมดสามารถแทนตัวเลขได้
ถ้าเป็นต้นไม้แบบนี้ −
นี่เป็นตัวแทนของสองเส้นทาง 21 และ 23 ดังนั้นผลลัพธ์จะเป็น 21 + 23 =44
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างฟังก์ชันเรียกซ้ำหนึ่งฟังก์ชันที่เรียกว่า dfs() ซึ่งจะทำการรูทและ num เริ่มแรก num =0
- ถ้าโหนดไม่เป็นโมฆะ
- num :=num * 10 + ค่าของโหนด
- ถ้าโหนดทางขวาไม่เป็นโมฆะ และโหนดทางซ้ายไม่เป็นโมฆะ ดังนั้น’
- sum :=sum + num
- num :=num / 10
- กลับจากฟังก์ชัน
- dfs(ด้านขวาของโหนด num)
- dfs(ด้านซ้ายของโหนด num)
- num :=num / 10
- กลับจากวิธีการ
- ผลรวมเริ่มต้น :=0
- เรียก dfs โดยใช้ root และ
- ผลตอบแทนรวม
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
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))
อินพุต
[2,1,3]
ผลลัพธ์
44
