題目連結: https://leetcode.com/problems/binary-tree-postorder-traversal/
Recursive version:
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]
}
Iterative version:
Hint: Postorder是LRV,實作iterative version時想成VRL,最後的結果陣列做reverse即可
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard let root = root else { return [] }
var stack: [TreeNode] = [root]
var result: [Int] = []
while !stack.isEmpty {
if let last = stack.last {
result.append(last.val)
stack.removeLast()
if let left = last.left {
stack.append(left)
}
if let right = last.right {
stack.append(right)
}
}
}
return result.reversed()
}