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

पायथन में लिंक्ड लिस्ट को जिग-जैग बाइनरी ट्री में बदलने का प्रोग्राम


मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट है, हमें इसे निम्न नियमों का उपयोग करके बाइनरी ट्री पथ में बदलना है:

  • लिंक्ड लिस्ट का हेड रूट है।
  • प्रत्येक बाद का नोड पैरेंट का बायां बच्चा है यदि उसका मान कम है, अन्यथा यह दायां बच्चा होगा।

उदाहरण के लिए, यदि इनपुट [2,1,3,4,0,5] है, तो आउटपुट ट्री होगा:

पायथन में लिंक्ड लिस्ट को जिग-जैग बाइनरी ट्री में बदलने का प्रोग्राम

समाधान दृष्टिकोण

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

  • एक फंक्शन solve() परिभाषित करें जो node लेता है
  • यदि node नल है: None लौटाएं
  • root := TreeNode(node.val) बनाएं
  • यदि node.next नल नहीं है:
    • यदि node.next.val < node.val:
      • root.left := solve(node.next)
    • अन्यथा:
      • root.right := solve(node.next)
  • root लौटाएं

उदाहरण कोड

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, node):
        if not node:
            return None
        root = TreeNode(node.val)
        if node.next:
            if node.next.val < node.val:
                root.left = self.solve(node.next)
            else:
                root.right = self.solve(node.next)
        return root

ob = Solution()
L = make_list([2,1,3,4,0,5])
print_tree(ob.solve(L))

इनपुट

[2,1,3,4,0,5]

आउटपुट

1, 3, 0, 5, 4, 2,

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

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

  1. Python में दिशाओं की सूची का उपयोग करके बाइनरी ट्री को पार करने का प्रोग्राम Python में दिशाओं की सूची का उपयोग करके बाइनरी ट्री को पार करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री और moves नामक स्ट्रिंग्स की एक सूची है जिसमें R (दाएं), L (बाएं) और U (ऊपर) शामिल हैं। रूट से शुरू करके, हमें moves में प्रत्येक चाल को निष्पादित करके ट्री को पार करना होगा जहां: R दाएं चाइल्ड को पार करने का संकेत देता है। L बाएं चाइल्ड को पार करने का संकेत देता ह

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

    मान लीजिए हमारे पास एक मान k और एक बाइनरी सर्च ट्री है, जहां प्रत्येक नोड या तो एक लीफ है या इसमें 2 बच्चे हैं। हमें मान k वाले नोड को खोजना है और उसके सिबलिंग का मान वापस करना है।इसलिए, यदि इनपुट इस तरह हैk = 4, तो आउटपुट 10 होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −एक फ़ंक्शन util