package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (nodes []int) {
	if root == nil {
		return
	}
	return postorderIteration(root)
}

func postorderRecurse(root *TreeNode, nodes *[]int) {
	if root == nil {
		return
	}
	postorderRecurse(root.Left, nodes)
	postorderRecurse(root.Right, nodes)
	*nodes = append(*nodes, root.Val)
}

func postorderIteration(root *TreeNode) (nodes []int) {
	stack := make([]*TreeNode, 0)
	for curr := root; ; {
		for curr != nil {
			if curr.Right != nil {
				stack = append(stack, curr.Right)
			}
			stack = append(stack, curr)
			curr = curr.Left
		} // Save right, root; visit left (the right node is saved to mark root.Right as unvisited)
		// curr is nil, pop top of stack
		curr = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// If right is not visited, pop right, save root again, and visit right
		if curr.Right != nil && len(stack) != 0 && curr.Right == stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
			stack = append(stack, curr)
			curr = curr.Right
		} else { // Else print root
			nodes = append(nodes, curr.Val)
			curr = nil
		}
		if len(stack) == 0 {
			break
		}
	}
	return
}

// func main() {
// 	fmt.Println(postorderTraversal(
// 		toBinaryTree(newInt(1), nil, newInt(2), newInt(3))))
// }