মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি এবং আরেকটি মান distance d আছে। দুটি ভিন্ন লিফ নোডের পেয়ারকে ভালো বলা হয় যখন তাদের মাঝপথের শর্টেস্ট পাথ দৈর্ঘ্য d-এর চেয়ে ছোট বা সমান হয়।
যেমন, ইনপুট যদি এমন হয়:
এবং distance d = 4, তবে আউটপুট হবে 2 কারণ পেয়ারগুলো হল (8,7) এবং (5,6) যাদের পাথ দৈর্ঘ্য ২, কিন্তু (7,5) বা (8,6) বা অন্য পেয়ারগুলো ভালো নয় কারণ তাদের পাথ দৈর্ঘ্য ৫ যা d = 4-র চেয়ে বড়।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- sol := 0
- একটি ফাংশন util() ডিফাইন করুন। এটি root নেবে:
- যদি root null হয়, তবে একটি খালি লিস্ট রিটার্ন করুন
- যদি root লিফ হয়, তবে [0, 0] পেয়ার ধারণকারী একটি অ্যারে রিটার্ন করুন
- অন্যথায়:
- cur := একটি নতুন লিস্ট
- l := util(root.left)
- r := util(root.right)
- l-এ থাকা প্রতিটি n জন্য n[1] := n[1] + 1
- r-এ থাকা প্রতিটি n জন্য n[1] := n[1] + 1
- r-এ থাকা প্রতিটি n এবং l-এ থাকা প্রতিটি n1 জন্য:
- যদি n[1] + n1[1] <= d হয়, তবে sol := sol + 1
- l+r রিটার্ন করুন
- মেইন মেথড থেকে util(root) কল করুন
- sol রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
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
