โปรแกรมค้นหาเส้นทางความยาว k บนต้นไม้ไบนารีใน Python

สมมติว่าเรามีต้นไม้ไบนารีที่มีค่าที่ไม่ซ้ำกันและเรามีค่าอื่น k เราต้องหาจำนวนเส้นทางที่ไม่ซ้ำกันความยาว k ในต้นไม้ เส้นทางสามารถไปได้ทั้งจากผู้ปกครองไปยังเด็กหรือจากเด็กไปยังผู้ปกครอง เราจะพิจารณาสองเส้นทางที่แตกต่างกันเมื่อบางโหนดปรากฏในเส้นทางหนึ่ง แต่ไม่ใช่อีกเส้นทางหนึ่ง

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

k =3 จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางคือ [12,8,3], [12,8,10], [8,12,15], [3,8,10]

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

• กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด

  • หากโหนดเป็นโมฆะ

    • กลับรายการที่มีเลข 1 และ k-1 เป็น 0s

  • ซ้าย :=dfs(ซ้ายของโหนด)

  • right :=dfs(ทางขวาของโหนด)

  • สำหรับผมอยู่ในช่วง 0 ถึง K ทำ

    • ans :=ans + left[i] * right[K - 1 - i]

  • res :=รายการขนาด K จาก 0s

  • res[0] :=1, res[1] :=1

  • สำหรับผมอยู่ในช่วง 1 ถึง K - 1 ทำ

    • res[i + 1] :=res[i + 1] + left[i]

    • res[i + 1] :=res[i + 1] + right[i]

  • ผลตอบแทน

• จากวิธีหลัก ให้ทำดังนี้−

• ตอบ :=0

• 
  

• dfs(root)

• 
  

• กลับมาอีกครั้ง

  
  

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

ตัวอย่าง

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