LeetCode – 145. Binary Tree Postorder Traversal

題目連結: 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()
    }