दो लीफ नोड्स का पेयर "गुड" है अगर उनके बीच का सबसे छोटा पथ ≤ d है। पोस्ट-ऑर्डर DFS से सभी गुड पेयर्स काउंट करें।
एल्गोरिदम
- रिकर्सिव
util(root)रिटर्न करता है: प्रत्येक लीफ के लिए[depth_from_root, 0](दूसरा मान अपडेट होता है)। - लेफ्ट और राइट सबट्री के लीफ्स के लिए: डेप्थ्स इन्क्रीमेंट करें।
- सभी लेफ्ट-राइट पेयर चेक करें: अगर
depth_left + depth_right <= dतो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]]
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
# टेस्ट: ट्री (लीफ्स: 8,7,5,6), d=4 -> गुड पेयर्स: (8,7), (5,6) -> आउटपुट: 2
इनपुट/आउटपुट
इनपुट: ट्री रूट, d=4
आउटपुट: 2
