সমস্যা বিবরণ
একটি বাইনারি ট্রি দেওয়া থাকে। প্রি-অর্ডার ট্রাভার্সাল দিয়ে স্ট্রিং বানান যেখানে নাল নোড = ()। অপ্রয়োজনীয় খালি প্যারেনথেসিস опуসর্ন করুন (one-to-one mapping বজায় রাখতে)।
উদাহরণ
ট্রি: ৫ (লেফ্ট: ৬ (রাইট: ৮), রাইট: ৭) → আউটপুট: "5(6()(8))(7)"
এলগরিদম (Recursive)
pot(node)ফাংশন:- নাল/০ হলে খালি স্ট্রিং রিটার্ন।
- লেফ্ট ও রাইট দুটোই নাল হলে শুধু
str(node.data)। s = str(node.data)।- লেফ্ট আছে →
s += '(' + pot(node.left) + ')', নাই →s += '()'। - রাইট আছে →
s += '(' + pot(node.right) + ')'। return s।
পাইথন বাস্তবায়ন
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def make_tree(elements):
root = TreeNode(elements[0])
for el in elements[1:]:
insert(root, el)
return root
def insert(root, data):
from collections import deque
q = deque([root])
while q:
node = q.popleft()
if not node.left:
node.left = TreeNode(data) if data is not None else TreeNode(0)
break
q.append(node.left)
if not node.right:
node.right = TreeNode(data) if data is not None else TreeNode(0)
break
q.append(node.right)
class Solution:
def tree2str(self, t):
def pot(node):
if not node or node.data == 0:
return ''
if not node.left and not node.right:
return str(node.data)
s = str(node.data)
if node.left:
s += '(' + pot(node.left) + ')'
else:
s += '()'
if node.right:
s += '(' + pot(node.right) + ')'
return s
return pot(t)
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root)) # 5(6()(8))(7)ইনপুট / আউটপুট
ইনপুট: [5,6,7,None,8] আউটপুট: 5(6()(8))(7)
