二叉树前中后序遍历总结
从前面的题目中可以看到,二叉树的前中后序遍历的递归方法是类似的,但是迭代的实现完全不同。
从垃圾回收的三色标记法得到启发,发现他们的共同点
- 节点入栈,标记为 0 ( 未访问 )
- 节点出栈,若已经访问,出栈。若未访问,标记为已访问,入栈。
- 节点左右节点 继续到 1
这样,我们可以通过控制节点的入栈顺序,用相似的代码来迭代完成二叉树的前中后序遍历。需要额外做的是多开一个On的空间来保存节点的状态
拿后序遍历做例子
1 | var postorderTraversal = function(root) { |