สมมติว่าเรามีไบนารีทรี เราต้องหาผลรวมของเส้นทแยงมุมแต่ละอันในต้นไม้โดยเริ่มจากบนลงล่างขวา
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น [27, 18, 3] เนื่องจากเส้นทแยงมุมคือ [12,15], [8,10],[3] ดังนั้นค่าผลรวมคือ [27, 18, 3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
กำหนดฟังก์ชัน traverse() สิ่งนี้จะใช้โหนด, numLeft, เอาต์พุต
-
หากโหนดเป็นโมฆะ
-
กลับ
-
-
ถ้า numLeft>=ขนาดของเอาต์พุต แล้ว
-
แทรกข้อมูลของโหนดที่ส่วนท้ายของเอาต์พุต
-
-
มิฉะนั้น
-
เอาต์พุต[numLeft] :=เอาต์พุต[numLeft] + ข้อมูลของโหนด
-
-
หากโหนดที่เหลือไม่เป็นโมฆะ
-
สำรวจ (ด้านซ้ายของโหนด numLeft+1 เอาต์พุต)
-
-
หากสิทธิ์ของโหนดไม่เป็นโมฆะ
-
สำรวจ (ด้านขวาของโหนด numLeft เอาต์พุต)
-
-
จากวิธีหลัก ให้ทำดังนี้ −
-
output :=รายการใหม่
-
traverse(root, 0, output)
-
ส่งคืนเอาต์พุต
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): output = [] def traverse(node, numLeft, output): if not node: return if numLeft >= len(output): output.append(node.data) else: output[numLeft] += node.data if node.left: traverse(node.left, numLeft+1, output) if node.right: traverse(node.right, numLeft, output) traverse(root, 0, output) return output ob = Solution() root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) print(ob.solve(root))
อินพุต
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10)
ผลลัพธ์
[27, 18, 3]
