二叉树前中后序遍历总结

从前面的题目中可以看到，二叉树的前中后序遍历的递归方法是类似的，但是迭代的实现完全不同。

从垃圾回收的三色标记法得到启发，发现他们的共同点

  1. 节点入栈，标记为 0 （ 未访问 ）
  2. 节点出栈，若已经访问，出栈。若未访问，标记为已访问，入栈。
  3. 节点左右节点 继续到 1 这样，我们可以通过控制节点的入栈顺序，用相似的代码来迭代完成二叉树的前中后序遍历。需要额外做的是多开一个On的空间来保存节点的状态

拿后序遍历做例子

var postorderTraversal = function(root) {
    var stack = [[root,0]]
    var res = []
    while(stack.length) {
        var [node,color] = stack.pop()
        if (color === 0) {
              // 在这里通过控制顺序就可以完成前中后序遍历            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
};