মান লইয়া আমাদের একটি বাইনারি ট্রি আছে, আমাদের ট্রির টপ ভিউ বের করতে হবে, সেগুলো লেফট-টু-রাইট সর্টেড থাকবে।
তবে, যদি ইনপুট হয় ইমেজের মতো, তবে আউটপুট হবে [3, 5, 8, 6, 9], কারণ 3, 2-এর উপরে আছে এবং 5, 7-এর উপরে আছে তাই সেগুলো দেখা যাবে না।
এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:
- view := একটি খালি ম্যাপ
- q := একটি ডবল-এন্ডেড কিউ
- q-তে (root, 0) পেয়ার পুশ করুন
- start := inf, end := -inf
- যদি q খালি না হয়:
- (node, coord) := q-এর লেফট এলিমেন্ট, তারপর লেফট এলিমেন্ট রিমুভ করুন
- start := min(start, coord)
- end := max(end, coord)
- যদি coord view-এ না থাকে, তবে view[coord] := node.val
- যদি node.left নাল না হয়, তবে (node.left, coord - 1) q-তে পুশ করুন
- যদি node.right নাল না হয়, তবে (node.right, coord + 1) q-তে পুশ করুন
- res := একটি খালি লিস্ট
- i = start থেকে end পর্যন্ত:
- যদি i view-এ থাকে, তবে view[i] res-এ অ্যাপেন্ড করুন
- res রিটার্ন করুন
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
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]
