मान लीजिए हमारे पास एक बाइनरी ट्री का इनऑर्डर और प्रीऑर्डर ट्रैवर्सल अनुक्रम है। हमें इन अनुक्रमों से ट्री उत्पन्न करना है। इसलिए यदि प्रीऑर्डर और इनऑर्डर अनुक्रम [3,9,20,15,7] और [9,3,15,20,7] हैं, तो ट्री होगा -

आइए चरण देखते हैं -
- मान लीजिए मेथड को buildTree कहा जाता है जिसमें प्रीऑर्डर और इनऑर्डर लिस्ट हैं
- root := प्रीऑर्डर से पहला नोड, और प्रीऑर्डर से पहला नोड हटाएं
- root_index := इनऑर्डर लिस्ट से root.val का इंडेक्स
- root का लेफ्ट := buildTree(प्रीऑर्डर, इनऑर्डर का सबसेट 0 से root_index तक)
- root का राइट := buildTree(प्रीऑर्डर, इनऑर्डर का सबसेट root_index + 1 से अंत तक)
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
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(object):
def buildTree(self, preorder, inorder):
if inorder:
root = TreeNode(preorder.pop(0))
root_index = inorder.index(root.data)
root.left = self.buildTree(preorder, inorder[:root_index])
root.right = self.buildTree(preorder, inorder[root_index+1:])
return root
ob1 = Solution()
print_tree(ob1.buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]))
इनपुट
[3,9,20,15,7] [9,3,15,20,7]
आउटपुट
9, 3, 15, 20, 7,