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

बाइनरी ट्री में दूसरा सबसे गहरा नोड ज्ञात करने का पायथन प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें दूसरे सबसे गहरे लीफ की गहराई ढूंढनी है। यदि कई सबसे गहरे लीफ हैं, तो दूसरा सबसे गहरा लीफ नोड अगला सबसे ऊंचा होगा। जैसा कि हम जानते हैं रूट की गहराई 0 होती है।

उदाहरण के लिए, यदि इनपुट इस तरह है:

बाइनरी ट्री में दूसरा सबसे गहरा नोड ज्ञात करने का पायथन प्रोग्राम

तो आउटपुट 1 होगा, क्योंकि दूसरा सबसे गहरा नोड 3 है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

  • यदि root नल है, तो
    • नल लौटाएं
  • nodes := एक नई सूची
  • root को nodes के अंत में डालें
  • count := 0, prev := 0, now := 0
  • जब तक nodes खाली नहीं है, करें
    • new := एक नई सूची
    • flag := सत्य
    • प्रत्येक node के लिए nodes में, करें
      • यदि flag सत्य है और (node का बायाँ नल है) और (node का दायाँ नल है), तो
        • prev := now
        • now := count
        • flag := असत्य
      • यदि node का बायाँ नल नहीं है, तो
        • node के बाएँ को new के अंत में डालें
      • यदि node का दायाँ नल नहीं है, तो
        • node के दाएँ को new के अंत में डालें
    • nodes := new
    • count := count + 1
  • prev लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

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):
        if root is None:
            return None
        nodes = []
        nodes.append(root)
        count = 0
        prev = 0
        now = 0
        while nodes:
            new = []
            flag = True
            for node in nodes:
                if flag and (not node.left) and (not node.right):
                    prev = now
                    now = count
                    flag = False
                if node.left:
                    new.append(node.left)
                if node.right:
                    new.append(node.right)
            nodes = new
            count += 1
        return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)

आउटपुट

1

  1. पायथन में ट्री के बाएं सबसे गहरे नोड को खोजने का प्रोग्राम पायथन में ट्री के बाएं सबसे गहरे नोड को खोजने का प्रोग्राम

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

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

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

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

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