双色标记法前中后遍历二叉树

发表于 | 分类于
用双色标记法完成统一的迭代

二叉树前中后序遍历总结

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

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

  1. 节点入栈，标记为 0 （ 未访问 ）
  2. 节点出栈，若已经访问，出栈。若未访问，标记为已访问，入栈。
  3. 节点左右节点 继续到 1

这样，我们可以通过控制节点的入栈顺序，用相似的代码来迭代完成二叉树的前中后序遍历。需要额外做的是多开一个On的空间来保存节点的状态

拿后序遍历做例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
};