Chương trình tìm số cặp nút lá tốt bằng Python

Giả sử chúng ta có một cây nhị phân. và khoảng cách giá trị khác d. Một cặp gồm hai nút lá khác nhau được cho là tốt, khi đường đi ngắn nhất giữa hai nút này nhỏ hơn hoặc bằng khoảng cách d.

Vì vậy, nếu đầu vào giống như

Và khoảng cách d =4, thì đầu ra sẽ là 2 vì các cặp là (8,7) và (5,6) vì khoảng cách chiều dài đường dẫn của chúng là 2, nhưng (7,5) hoặc (8,6) hoặc các cặp khác không tốt vì độ dài đường dẫn của chúng là 5 lớn hơn d =4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sol:=0

• Định nghĩa một hàm dùng (). Điều này sẽ bắt nguồn từ gốc

• nếu root là null thì

  • trả lại một danh sách mới

• nếu rễ là lá thì

  • trả về một mảng có một cặp [0, 0]

• nếu không,

  • cur:=một danh sách mới

  • l:=use (bên trái của thư mục gốc)

  • r:=use (bên phải của thư mục gốc)

  • cho mỗi n trong l, làm

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

  • với mỗi n trong r, thực hiện

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

  • với mỗi n trong r, thực hiện

    • đối với mỗi n1 trong l, thực hiện

      • nếu n [1] + n1 [1] <=d, thì

        • sol:=sol + 1

  • trả về l + r

• Từ phương thức chính, hãy làm như sau -

• sử dụng (root)

• trả lại sol

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

2