颜色标记法(转自LeetCode-henry)
兼具栈迭代方法的高效,又像递归方法一样简洁易懂,更重要的是,这种方法对于前序、中序、后序遍历,能够写出完全一致的代码。
其核心思想如下:
使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。
解释一下为什么需要“右子节点、自身、左子节点依次入栈”
我们有一棵二叉树:
中
/ \
左 右
前序遍历:中,左,右
中序遍历:左,中,右
后序遍历:左,右,中
本题需要中序遍历。
栈是一种 先进后出的结构,出栈顺序为左,中,右
那么入栈顺序必须调整为倒序,也就是右,中,左
同理,如果是前序遍历,入栈顺序为 右,左,中;后序遍历,入栈顺序中,右,左