परिचय
मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री का टॉप व्यू (top view) ढूंढना है, वे बाएं-से-दाएं सॉर्टेड होंगे।
तो, यदि इनपुट छवि जैसा है, तो आउटपुट [3, 5, 8, 6, 9] होगा, क्योंकि 3, 2 के ऊपर है और 5, 7 के ऊपर है इसलिए वे दिखाई नहीं देते।
समाधान दृष्टिकोण
लेवल ऑर्डर ट्रैवर्सल (BFS) का उपयोग करते हुए हॉरिजॉन्टल डिस्टेंस (HD) ट्रैक करें। प्रत्येक HD के लिए पहला नोड (टॉपमोस्ट) टॉप व्यू का हिस्सा होता है।
उदाहरण कोड
from collections import deque
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
view = {}
q = deque()
q.append((root, 0))
start = float("inf")
end = float("-inf")
while q:
node, coord = q.popleft()
start = min(start, coord)
end = max(end, coord)
if coord not in view:
view[coord] = node.val
if node.left:
q.append((node.left, coord - 1))
if node.right:
q.append((node.right, coord + 1))
res = []
for i in range(start, end + 1):
if i in view:
res.append(view[i])
return res
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(2)
root.right.right.right = TreeNode(9)
print(ob.solve(root))
इनपुट
root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(8) root.right.left = TreeNode(7) root.right.right = TreeNode(6) root.right.left.left = TreeNode(2) root.right.right.right = TreeNode(9)
आउटपुट
[3, 5, 8, 6, 9]
निष्कर्ष
BFS + हॉरिजॉन्टल डिस्टेंस ट्रैकिंग का उपयोग करके टॉप व्यू O(n) समय में निकाला जाता है। प्रत्येक HD के लिए पहला एनकाउंटर किया गया नोड टॉप व्यू में होता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।