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

पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक पूर्णांक k है, हमें ट्री में kवां सबसे छोटा मान ढूंढना है।

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

पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम

k = 3, तो आउटपुट 7 होगा।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (इटरेटिव इनऑर्डर ट्रैवर्सल):

  • stack := [], i := 0, ans := -1।

  • जब तक stack खाली नहीं है या root null नहीं है:

    • जब तक root null नहीं है:

      • stack.append(root); root = root.left।

    • v := stack.pop()।

    • यदि i == k, तो ans = v.val और लूप से बाहर निकलें।

    • root = v.right; i += 1।

  • ans लौटाएं।

उदाहरण

class TreeNode:    def __init__(self, value):       self.val = value       self.left = None       self.right = None class Solution:    def solve(self, root, k):       stack = []       i = 0       ans = -1       while stack or root:          while root:             stack.append(root)                root = root.left          v = stack.pop()          if i == k:             ans = v.val             break          root = v.right          i += 1       return ans ob = Solution() root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.right.left = TreeNode(7) root.right.right = TreeNode(15) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root, 3))

इनपुट

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

आउटपुट

7

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

    मान लीजिए हमारे पास एक दिया गया बाइनरी ट्री है; हमें उस दिए गए बाइनरी ट्री में सबसे बड़े परफेक्ट सब-ट्री का आकार ढूंढना है। जैसा कि हम जानते हैं, परफेक्ट बाइनरी ट्री एक बाइनरी ट्री है जिसमें सभी आंतरिक नोड्स के दो बच्चे होते हैं और सभी पत्ते समान स्तर पर होते हैं।तो, यदि इनपुट इस तरह है:तो आउटपुट 3

  1. Python प्रोग्राम से सूची में सबसे छोटी संख्या खोजना Python प्रोग्राम से सूची में सबसे छोटी संख्या खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक सूची दी गई है, हमें सूची में उपलब्ध सबसे छोटी संख्या प्रदर्शित करने की आवश्यकता है। यहां हम या तो सूची को क्रमबद्ध करके सबसे छोटा तत्व प्राप्त कर सकते हैं या बिल्ट-इन min() फ़ंक्शन का उपयोग करके सबसे छोटा तत्

  1. Python प्रोग्राम से ऐरे में सबसे बड़ा तत्व खोजना Python प्रोग्राम से ऐरे में सबसे बड़ा तत्व खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक ऐरे दिया गया है, हमें ऐरे के सबसे बड़े तत्व की गणना करने की आवश्यकता है। यहां हम ब्रूट-फोर्स दृष्टिकोण का उपयोग करते हैं जिसमें हम पूरे लूप को पार करके और तत्व प्राप्त करके सबसे बड़ा तत्व निकालते हैं। हम नीच