# ac solution code

• Solution. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)

Explanation

Postorder: left, right, root
Preorder : root, right, left

Postorder is kind of reverse order of Preorder. (Just travel to tree's right leaf at first, instead of left leaf).

1. Start from root, recursively travel to each passed node's right child until reach the tree's right leaf
2. Then pop to right leaf's higher level node A
3. And switch to A's left branch

Keep the above steps until the current node is null and stack is empty.

Trick: Add node's value to array's first position to reverse the order.

``````/*
Solution1. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)
*/
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
var stack = Stack<TreeNode>()
var cur: TreeNode? = root           // Set `root` as `cur`

while cur != nil || !stack.isEmpty {// <-- !stack.isEmpty
if cur != nil {                 // 1. Push cur's RIGHT branch to stack until leaf
res.insert(cur!.val, at: 0) // 2. Insert cur's val at 0
stack.push(cur!)
cur = cur!.right
} else {
cur = stack.pop()           // 3. Backtrack to higher level node A (stack isn't empty, via while/if condition)
cur = cur!.left             // 4. Switch to the higher node A's LEFT branch
}
}
return res
}

``````

``````    /*
Solution2. Translate from recusive solution. time = O(n) - each node is visited once; space = O(n)
CAN'T BE USED for in-order traversal, because root poping is after all left nodes poping (root poping is at beginning for Pre/Post traversal)
*/
func postorderTraversal(_ root: TreeNode?) -> [Int] {
var res = [Int]()
guard let root = root else {return res}
var stack = Stack<TreeNode>()
stack.push(root)                    // Push: root

while !stack.isEmpty() {
let curr = stack.pop()!         // Pop: the last pushed node
res.insert(curr.val, at: 0)     // <--insert at 0
if curr.left != nil {           // Push: curr.left
stack.push(curr.left!)
}
if curr.right != nil{           // <--Push: curr.right later than curr.left (Stack reverses order of execution)
stack.push(curr.right!)
}
}
return res
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.