โปรแกรมค้นหาจำนวนคู่ลีฟโหนดที่ดีโดยใช้ Python

สมมติว่าเรามีต้นไม้ไบนารี และอีกค่าระยะทางd. มีการกล่าวกันว่าโหนดลีฟที่แตกต่างกันสองคู่นั้นดี เมื่อเส้นทางที่สั้นที่สุดระหว่างโหนดทั้งสองนี้มีขนาดเล็กกว่าหรือเท่ากับระยะทาง d

ดังนั้นหากอินพุตเป็นแบบ

และระยะทาง d =4 แล้วเอาต์พุตจะเป็น 2 เพราะทั้งคู่คือ (8,7) และ (5,6) เนื่องจากระยะทางของความยาวเส้นทางคือ 2 แต่ (7,5) หรือ (8,6) หรือคู่อื่น ไม่ดีเพราะความยาวของเส้นทางคือ 5 ซึ่งมากกว่า d =4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• โซล :=0

• กำหนดฟังก์ชัน util() สิ่งนี้จะหยั่งราก

• ถ้ารูทเป็นโมฆะ

  • กลับรายการใหม่

• ถ้ารากเป็นใบ

  • คืนค่าอาร์เรย์หนึ่งคู่ [0, 0]

• มิฉะนั้น

  • cur :=รายการใหม่

  • l :=util(ซ้ายของรูท)

  • r :=util(ทางขวาของรูท)

  • สำหรับแต่ละ n ใน l ทำ

    • n[1] :=n[1] + 1

  • สำหรับแต่ละ n ใน r ทำ

    • n[1] :=n[1] + 1

  • สำหรับแต่ละ n ใน r ทำ

    • สำหรับแต่ละ n1 ใน l ทำ

      • ถ้า n[1] + n1[1] <=d แล้ว

        • โซล :=โซล + 1

  • กลับ l+r

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• util(root)

• กลับโซล

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class TreeNode:
def __init__(self, val=0, left=None, right=None):
   self.val = val
   self.left = left
   self.right = right
class Solution:
   def __init__(self):
      self.sol = 0
   def solve(self, root, d):
      def util(root):
         if not root:
            return []
         if not root.left and not root.right:
            return [[0, 0]]
         else:
            cur = []
            l = util(root.left)
            r = util(root.right)
            for n in l:
               n[1] += 1
            for n in r:
               n[1] += 1
            for n in r:
               for n1 in l:
                  if n[1] + n1[1] <= d:
                     self.sol += 1
            return l+r
      util(root)
      return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))

อินพุต

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4

ผลลัพธ์

2