สมมติว่าเรามีไบนารีทรี เราต้องหาผลรวมทรีย่อยที่บ่อยที่สุด ผลรวมทรีย่อยของโหนดคือผลรวมของค่าทั้งหมดภายใต้โหนด ซึ่งรวมถึงตัวโหนดด้วย
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น 3 เมื่อมันเกิดขึ้นสองครั้ง – หนึ่งครั้งในฐานะลีฟด้านซ้าย และอีกครั้งหนึ่งเป็นผลรวมของ 3 - 6 + 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- นับ :=แผนที่ว่างเปล่า
- กำหนดฟังก์ชัน getSum() นี่จะใช้โหนด
- ถ้าโหนดเป็น null แล้ว
- คืน 0
- mySum :=getSum(ซ้ายของโหนด) + getSum(ทางขวาของโหนด) + ค่าของโหนด
- นับ[mySum] :=นับ[mySum] + 1
- คืน mySum
- จากวิธีหลักให้ทำดังนี้
- getSum(ราก)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
จากคอลเลกชั่น นำเข้า defaultdictclass TreeNode:def __init__(self, data, left =None, right =None):self.val =data self.left =left self.right =rightclass วิธีแก้ไข:def แก้ (ตนเอง, รูท):count =defaultdict(int) def getSum(node):ถ้าไม่ใช่ node:return 0 mySum =getSum(node.left) + getSum(node.right) + node.val count[mySum] +=1 return mySum getSum(root) คืนค่าสูงสุด (นับ คีย์=นับ.get)ob =โซลูชัน ()รูท =TreeNode(-6)root.left =TreeNode(3)root.right =TreeNode(6) พิมพ์ (ob.solve (รูท))อินพุต
root =TreeNode(-6)root.left =TreeNode(3)root.right =TreeNode(6)ผลลัพธ์
3
