สมมติว่ามีต้นไม้ไบนารีที่มีค่าไม่ซ้ำ และมีค่า k เราต้องหาจำนวนเส้นทางที่ไม่ซ้ำกันความยาว k ในต้นไม้ เส้นทางสามารถไปจากพ่อไปลูกหรือลูกไปพ่อ สองเส้นทางถือว่าต่างกันถ้ามีโหนดปรากฏในอันหนึ่งแต่อีกอันไม่มี
เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ k = 3 ผลลัพธ์จะเป็น 4 เส้นทางคือ [12,8,3], [12,8,10], [8,12,15], [3,8,10]
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน dfs() รับ node
- ถ้า node เป็น null คืนค่ารายการ [1] + [0]*(K-1)
- left := dfs(left of node), right := dfs(right of node)
- for i ในช่วง 0 ถึง K ans := ans + left[i] * right[K-1-i]
- res := รายการขนาด K เติม 0, res[0] := 1, res[1] := 1
- for i ในช่วง 1 ถึง K-1 res[i+1] += left[i] + right[i]
- คืนค่า res
- จากเมธอดหลัก ans := 0 เรียก dfs(root) คืนค่า ans
ตัวอย่างโค้ด
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, K):
def dfs(node):
if not node:
return [1] + [0] * (K-1)
left = dfs(node.left)
right = dfs(node.right)
for i in range(K):
self.ans += left[i] * right[K - 1 - i]
res = [0] * K
res[0] = res[1] = 1
for i in range(1, K - 1):
res[i + 1] += left[i]
res[i + 1] += right[i]
return res
self.ans = 0
dfs(root)
return self.ans
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, 3))
อินพุต
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 3
เอาต์พุต
4
