Cho cây nhị phân, tìm duyệt hậu thứ tự (postorder: trái → phải → gốc) bằng phương pháp lặp (iterative).
Ví dụ cây: [-10,9,10,None,None,15,7] → kết quả: [9, 15, 7, 10, -10].
Giải thuật (Stack + State)
Dùng stack lưu cặp (node, state) với state=0 (chưa xử lý con), state=1 (đã xử lý con, sẵn sàng thêm vào kết quả).
- Push (root, 0).
- Khi pop:
- Nếu state=0: push (node, 1), sau đó push (right, 0) và (left, 0) nếu có.
- Nếu state=1: thêm node.val vào kết quả.
Ví dụ triển khai Python
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):
root = TreeNode(elements[0])
for el in elements[1:]:
insert(root, el)
return root
class Solution:
def postorderTraversal(self, root):
if not root:
return []
res = []
stack = [[root, 0]]
while stack:
node, state = stack.pop()
if state == 0:
stack.append([node, 1])
if node.right:
stack.append([node.right, 0])
if node.left:
stack.append([node.left, 0])
else:
if node.data != 0: # bỏ qua node giả (0)
res.append(node.data)
return res
ob = Solution()
root = make_tree([-10, 9, 10, None, None, 15, 7])
print(ob.postorderTraversal(root)) # [9, 15, 7, 10, -10]Đầu vào / Đầu ra
Input: [-10, 9, 10, None, None, 15, 7] Output: [9, 15, 7, 10, -10]