สมมติว่าเรามีไบนารีทรี เราต้องหาทรีเดียวกัน แต่ค่าของโหนดทุกอันจะถูกแทนที่ด้วยค่าของมัน + ผลรวมของทรีย่อยด้านซ้ายและขวาทั้งหมด
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์ที่ได้จะเป็น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน tree_sum() นี้จะหยั่งรากของต้นไม้
-
ถ้ารูทเป็นโมฆะ
-
คืนค่า 0
-
-
ข้อมูลของรูท :=tree_sum(ซ้ายของรูท) + tree_sum(ทางขวาของรูท) + ข้อมูลของรูท
-
ส่งคืนข้อมูลของรูท
-
จากวิธีหลัก ให้ทำดังนี้:
-
tree_sum(ราก)
-
คืนค่ารูท
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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: TreeNode): 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)
อินพุต
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10)
ผลลัพธ์
9, 19, 7, 25, 4,
