দুটি ট্রাভার্সাল সিকোয়েন্স প্রিঅর্ডার এবং পোস্টঅর্ডার দেওয়া আছে। এগুলো থেকে বাইনারি ট্রি জেনারেট করতে হবে।
সিকোয়েন্স: [1,2,4,5,3,6,7], [4,5,2,6,7,3,1]
সমাধানের ধাপসমূহ
- ans := pre[0] ভ্যালু দিয়ে ট্রি নোড, stack := খালি, ans পুশ
- i := 1, j := 0
- যখন i < len(pre) এবং j < len(post):
- যদি stack[-1].data == post[j]: j++, stack.pop(), কন্টিনিউ
- node := pre[i] ভ্যালু দিয়ে ট্রি নোড
- যদি stack[-1].left খালি: stack[-1].left = node, অন্যথায় stack[-1].right = node
- node পুশ, i++
- ans রিটার্ন
উদাহরণ
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def height(root):
if root is None:
return 0
l_height = height(root.left)
r_height = height(root.right)
if l_height > r_height:
return l_height + 1
else:
return r_height + 1
def print_given_level(root, level):
if root is None:
return
if level == 1:
print(root.data, end=',')
elif level > 1:
print_given_level(root.left, level-1)
print_given_level(root.right, level-1)
def level_order(root):
print('[', end='')
h = height(root)
for i in range(1, h+1):
print_given_level(root, i)
print(']')
class Solution(object):
def constructFromPrePost(self, pre, post):
ans = TreeNode(pre[0])
stack = [ans]
i = 1
j = 0
while i < len(pre) and j < len(post):
if stack[-1].data == post[j]:
j += 1
stack.pop(-1)
continue
node = TreeNode(pre[i])
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
i += 1
return ans
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree)
ইনপুট
[1,2,4,5,3,6,7] [4,5,2,6,7,3,1]
আউটপুট
[1,2,3,4,5,6,7,]
