สมมติว่ามีต้นไม้ไบนารี เราต้องหาผลรวมของแต่ละเส้นทแยงในต้นไม้เริ่มจากด้านบนไปขวาล่าง
เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ ผลลัพธ์จะเป็น [27, 18, 3] เนื่องจากเส้นทแยงคือ [12,15], [8,10], [3] ผลรวมคือ [27, 18, 3]
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน traverse() รับ node, numLeft, output
- ถ้า node เป็น null คืนค่า
- ถ้า numLeft >= ขนาดของ output ใส่ข้อมูลของ node เข้า output
- มิฉะนั้น output[numLeft] := output[numLeft] + ข้อมูลของ node
- ถ้า left of node ไม่ใช่ null เรียก traverse(left of node, numLeft+1, output)
- ถ้า right of node ไม่ใช่ null เรียก traverse(right of node, numLeft, output)
- จากเมธอดหลัก output := รายการใหม่ เรียก traverse(root, 0, output) คืนค่า 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]
