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

पायथन में ट्री के इनऑर्डर अनुक्रम के पैलिंड्रोम होने की जांच करने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी ट्री है जहां प्रत्येक नोड में 0-9 से एक अंक होता है, हमें जांचना है कि इसका इन-ऑर्डर ट्रैवर्सल पैलिंड्रोम है या नहीं।

इसलिए, यदि इनपुट इस तरह है

पायथन में ट्री के इनऑर्डर अनुक्रम के पैलिंड्रोम होने की जांच करने का प्रोग्राम

तो आउटपुट True होगा, क्योंकि इसका इनऑर्डर ट्रैवर्सल [2,6,10,6,2] है।

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

  • यदि root null है, तो
    • True वापस करें
  • stack := एक नया स्टैक
  • curr := root
  • inorder := एक नई सूची
  • जब तक stack खाली नहीं है या curr null नहीं है, करें
    • जब तक curr null नहीं है, करें
      • curr को stack में पुश करें
      • curr := curr का बायाँ
    • node := stack से पॉप किया गया तत्व
    • node के मान को inorder के अंत में जोड़ें
    • curr := node का दायाँ
  • यदि inorder, उल्टे क्रम में inorder के समान है तो true वापस करें, अन्यथा false।

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

उदाहरण

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):       if not root:          return True       stack = []       curr = root       inorder = []       while stack or curr:          while curr:             stack.append(curr)             curr = curr.left          node = stack.pop() inorder.append(node.val)          curr = node.right       return inorder == inorder[::-1] ob = Solution() root = TreeNode(6) root.left = TreeNode(2) root.right = TreeNode(6) root.right.left = TreeNode(10) root.right.right = TreeNode(2) print(ob.solve(root))

इनपुट

root = TreeNode(6) root.left = TreeNode(2) root.right = TreeNode(6) root.right.left = TreeNode(10) root.right.right = TreeNode(2)

आउटपुट

True

  1. पायथन में बाइनरी ट्री के पूर्ण होने की जांच करने का प्रोग्राम पायथन में बाइनरी ट्री के पूर्ण होने की जांच करने का प्रोग्राम

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

  1. पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

    मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो। उदाहरण के लिए, यदि

  1. पायथन में जांचें कि क्या कोई मान BST में मौजूद है या नहीं पायथन में जांचें कि क्या कोई मान BST में मौजूद है या नहीं

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक अन्य इनपुट val है, हमें जांचना है कि क्या val ट्री में मौजूद है या नहीं। उदाहरण के लिए, यदि इनपुट है: val = 7, तो आउटपुट होगा True, क्योंकि 7 ट्री में मौजूद है। हल करने के चरण एक फ़ंक्शन solve() परिभाषित करें। यह root, val लेगा। यदि root नल है, तो Fal