Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

Python में बाइनरी ट्री का टॉप व्यू ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री का टॉप व्यू (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 के लिए पहला एनकाउंटर किया गया नोड टॉप व्यू में होता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. पायथन में बाइनरी ट्री पर k-लंबाई के पथ खोजने का प्रोग्राम पायथन में बाइनरी ट्री पर k-लंबाई के पथ खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें अद्वितीय मान हैं और हमारे पास एक अन्य मान k है, हमें ट्री में k-लंबाई के अद्वितीय पथों की संख्या ढूंढनी है। पथ पैरेंट से चाइल्ड या चाइल्ड से पैरेंट की ओर जा सकते हैं। हम दो पथों को अलग मानेंगे जब कोई नोड एक पथ में दिखाई देता है लेकिन दूसरे में नहीं। उदाह

  1. पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट नोड से लीफ नोड तक जाने वाले किसी भी पथ का सबसे बड़ा योग ढूंढना है। उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट 29 होगा क्योंकि रूट से, यदि हम पथ 5-<9-<7-<8 का पालन करते हैं तो जोड़ के बाद यह 29 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

  1. पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ढूंढनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो बाएं सबसे नोड और दाएं सबसे नोड के बीच रखे जा सकते हैं। उदाहरण के लिए, यदि इनपुट है: तो आउटपुट होगा 2। हल करने के चरण एक मैप d बनाएं, न्यूनतम और अधिकतम मान