একটি বাইনারি ট্রি দেওয়া থাকে। এর মিরর ইমেজ (ইনভার্টেড ট্রি) তৈরি করতে হবে। বাম এবং ডান চাইল্ড সোয়াপ করে রিকারসিভলি সমাধান করতে হবে।
সমাধানের পদ্ধতি
- যদি রুট নাল হয়, রিটার্ন করুন।
- বাম এবং ডান পয়েন্টার সোয়াপ করুন।
- বাম এবং ডান সাবট্রির জন্য রিকারসিভলি কল করুন।
উদাহরণ কোড
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while len(que):
temp = que[0]
que.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def height(root):
if root is None:
return 0
l_height = height(root.left)
r_height = height(root.right)
return max(l_height, 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):
h = height(root)
for i in range(1, h + 1):
print_given_level(root, i)
class Solution(object):
def invertTree(self, root):
self.solve(root)
return root
def solve(self, root):
if not root:
return
temp = root.left
root.left = root.right
root.right = temp
self.solve(root.left)
self.solve(root.right)
tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
tree2 = ob1.invertTree(tree1)
level_order(tree2)
ইনপুট
[1,2,2,3,4,None,3]
আউটপুট
1,2,2,3,None,4,3,
