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

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

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

तो आउटपुट [5, 4, 10, 2, 7, 15, ] होगा।

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

head := एक नया लिंक्ड लिस्ट नोड (डमी)।
currNode := head।
q := [root] वाली एक क्यू बनाएं।
जब तक q खाली नहीं है:
- curr := q से पहला तत्व निकालें।
- यदि curr null नहीं है:
  - currNode.next := ListNode(curr.val)।
  - currNode := currNode.next।
  - curr.left और curr.right को q के अंत में जोड़ें।
head.next लौटाएं।

उदाहरण

class ListNode:    def __init__(self, data, next = None):       self.val = data       self.next = next class TreeNode:    def __init__(self, data, left = None, right = None):       self.val = data       self.left = left       self.right = right def print_list(head):    ptr = head    print('[', end = "")    while ptr:       print(ptr.val, end = ", ")       ptr = ptr.next print(']')     class Solution:    def solve(self, root):       head = ListNode(None)       currNode = head       q = [root]       while q:          curr = q.pop(0)          if curr:             currNode.next = ListNode(curr.val)             currNode = currNode.next             q.append(curr.left)             q.append(curr.right)       return head.next ob = Solution() root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(2) root.right.left = TreeNode(7) root.right.right = TreeNode(15) head = ob.solve(root) print_list(head)

इनपुट

root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(2) root.right.left = TreeNode(7) root.right.right = TreeNode(15) head = ob.solve(root)

आउटपुट

[5, 4, 10, 2, 7, 15, ]