กำหนด binary tree ต้องหา postorder traversal (left, right, root) แบบ iterative (ไม่ใช้ recursion)
ตัวอย่าง tree: root=-10, left=9, right=10, right.left=15, right.right=7 → output [9,15,7,10,-10]
ขั้นตอนการแก้ปัญหา
- ถ้า root เป็น None คืนลิสต์ว่าง
- ใช้ stack เก็บ pair [node, state] โดย state=0 คือยังไม่ได้ประมวลผลลูก, state=1 คือประมวลผลลูกแล้วพร้อมเพิ่มในผลลัพธ์
- while stack ไม่ว่าง: pop ดู state, ถ้า 0 ให้ push [node,1] แล้ว push right และ left (ถ้ามี) ด้วย state=0
- ถ้า state=1 และ node.data != 0 ให้ append node.data ลงผลลัพธ์
ตัวอย่างโค้ด
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[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
class Solution(object):
def postorderTraversal(self, root):
if not root:
return []
res = []
stack = [[root, 0]]
while stack:
node = stack[-1]
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]
