मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें अद्वितीय मान हैं और हमारे पास एक अन्य मान k है, हमें ट्री में k-लंबाई के अद्वितीय पथों की संख्या ढूंढनी है। पथ पैरेंट से चाइल्ड या चाइल्ड से पैरेंट की ओर जा सकते हैं। हम दो पथों को अलग मानेंगे जब कोई नोड एक पथ में दिखाई देता है लेकिन दूसरे में नहीं।
उदाहरण के लिए, यदि इनपुट जैसा है:
k = 3, तो आउटपुट 4 होगा, क्योंकि पथ हैं [12,8,3], [12,8,10], [8,12,15], [3,8,10]।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- dfs() फंक्शन परिभाषित करें जो node लेता है:
- यदि node null है, तो 1 और k-1 शून्यों वाली सूची वापस करें
- left := dfs(node का बायां)
- right := dfs(node का दायां)
- i को 0 से K तक के लिए करें:
- ans := ans + left[i] * right[K-1-i]
- res := आकार K की शून्यों वाली सूची
- res[0] := 1, res[1] := 1
- i को 1 से K-1 तक के लिए करें:
- res[i+1] := res[i+1] + left[i]
- res[i+1] := res[i+1] + right[i]
- res वापस करें
- मुख्य विधि से:
- ans := 0
- dfs(root)
- ans वापस करें
उदाहरण
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