একটি বাইনারি ট্রি দেওয়া আছে। এর পোস্ট-অর্ডার ট্রভার্সাল (বাম, ডান, রুট) ইটেরেটিভ পদ্ধতিতে বের করুন।
উদাহরণ: ট্রি [-10,9,10,None,None,15,7] -> আউটপুট [9,15,7,10,-10]।
সমাধানের ধাপসমূহ
- যদি রুট null, খালি লিস্ট রিটার্ন।
- স্ট্যাক ব্যবহার করুন: pair [node, state] (state 0=প্রথমবার, 1=প্রক্রিয়া করা) 찔ে।
- যখন state 0: নোডকে state 1 দিয়ে পুশ, তারপর ডান ও বাম সন্তানকে state 0 দিয়ে পুশ।
- যখন state 1: নোডের মান রেজাল্টে যোগ করুন।
পাইথন কোড উদাহরণ
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = [temp]
while que:
temp = que.pop(0)
if not temp.left:
temp.left = TreeNode(data) if data is not None else TreeNode(0)
break
else: que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data) if data is not None else 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
class Solution:
def postorderTraversal(self, root):
if not root: return []
res = []
stack = [[root, 0]]
while stack:
node = stack.pop()
if node[1] == 0:
current = node[0]
stack.append([current, 1])
if current.right: stack.append([current.right, 0])
if current.left: stack.append([current.left, 0])
else:
if node[0].data != 0: res.append(node[0].data)
return res
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.postorderTraversal(root))
ইনপুট
[-10,9,10,None,None,15,7]
আউটপুট
[9, 15, 7, 10, -10]
