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

二叉树前中后序遍历总结

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

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

  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
};