As you can see from the previous questions, the recursive methods for front-, middle-, and post-order traversal of a binary tree are similar, but the iterative implementation is completely different.

Get inspired by the three-color marking method of garbage collection and find their common points

  1. Push the node onto the stack and mark it as 0 (unvisited).
  2. Pop the node off the stack. If it has been visited, pop it. If it has not been visited, mark it as visited and push it onto the stack.
  3. Continue with the left and right nodes to 1. In this way, we can use similar code to iteratively traverse a binary tree in front, middle, and back order by controlling the order in which we push the nodes onto the stack. All we need to do is create an additional On space to store the node status.

Take post-order traversal as an example

var postorderTraversal = function(root) {
    var stack = [[root,0]]
    var res = []
    while(stack.length) {
        var [node,color] = stack.pop()
        if (color === 0) {
              // Here, we can complete the front-middle-post order traversal by controlling the order stack.push([node,1])
            node.right && stack.push([node.right,0])
            node.left && stack.push([node.left,0])
        } else {
            res.push(node.val)
        }
    }
    return res
};