สมมติว่าเรามีไบนารีทรีและค่า k อีกค่าหนึ่ง เราต้องหาจำนวนโหนดที่ไม่ซ้ำกันไปยังพาธย่อยย่อยซึ่งมีค่าเท่ากับ k
ดังนั้นหากอินพุตเป็นแบบ
และ k =5 ดังนั้นผลลัพธ์จะเป็น 2 เนื่องจากเส้นทางคือ [2, 3] และ [1, 4]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- จำนวน :=แผนที่เริ่มเก็บค่า 1 สำหรับคีย์ 0
- แทน :=0, คำนำหน้า :=0
- กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด
- ถ้าโหนดไม่เป็นโมฆะ
- คำนำหน้า :=คำนำหน้า + ค่าของโหนด
- ans :=ans + (count[prefix - target] ถ้าไม่สามารถใช้ได้ จะเป็น 0)
- นับ[คำนำหน้า] :=นับ[คำนำหน้า] + 1
- dfs(ด้านซ้ายของโหนด)
- dfs(ด้านขวาของโหนด)
- นับ[คำนำหน้า] :=นับ[คำนำหน้า] - 1
- prefix :=prefix - ค่าของโหนด
- จากวิธีหลัก ให้ทำดังนี้
- dfs(root)
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
จากคอลเลกชั่นนำเข้า Counterclass TreeNode:def __init__(self, data, left =None, right =None):self.val =data self.left =left self.right =rightclass Solution:def Solve(ตัวเอง รูท เป้าหมาย ):count =Counter([0]) ans =prefix =0 def dfs(node):nonlocal ans, prefix if node:prefix +=node.val ans +=count[prefix - target] count[prefix] +=1 dfs(node.left) dfs(node.right) count[prefix] -=1 prefix -=node.val dfs(root) return ans ob =Solution()root =TreeNode(3)root.left =TreeNode(2) root.right =TreeNode(4)root.right.left =TreeNode(1)root.right.left.right =TreeNode(2)k =5print(ob.solve(root, k))
อินพุต
root =TreeNode(3)root.left =TreeNode(2)root.right =TreeNode(4)root.right.left =TreeNode(1)root.right.left.right =TreeNode(2)5ผลลัพธ์
2
