说到二叉树的遍历，递归写法大家都觉得挺优雅的，前中后序也就是调调节点顺序的事。但一旦切换到迭代法，事情就开始变得拧巴了——前序和后序勉强能用一套逻辑写下来，中序却完全是另一套玩法，一会儿栈，一会儿指针，折腾半天写出来三套风格各异的代码。
不过其实，迭代法也能写出统一风格的代码，关键就在于一个很巧妙的小技巧：标记法。
先说原因。之前用栈模拟迭代遍历时，碰到的核心矛盾是：访问节点和处理节点的时机不一致。中序遍历需要先“路过”根节点，但只有当左子树处理完，才能回头处理根节点——而栈的后进先出特性，让它很难同时处理好“路过”和“处理”这两个动作。
那怎么解决？简单粗暴：把要处理的节点也扔进栈里，但做个标记。具体做法是，当某个节点需要“被处理”（即加入结果集）时，我们往栈里再塞一个空指针作为哨兵。
来看中序遍历的代码，配合动画更容易理解：
class Solution {
public:
vector
动画中，result数组就是最终结果集。
核心逻辑是这样：我们先把所有节点（包括根节点）当作“待访问”的节点入栈。当碰到一个非空节点时，它还不急着处理，而是跟着它的右、中、左子节点一起再按顺序入栈，同时在中节点后面加一个空指针作为标记。只有当弹出的是一个空指针时，才说明栈顶的下一个节点已经被访问过，可以放进结果集了。
这个思路一打通，前序和后序就简单了：只需要调整入栈顺序就行。
迭代法前序遍历
前序遍历和中序遍历相比，仅仅改变了两行代码的顺序：
class Solution {
public:
vector
迭代法后序遍历
后序遍历也一样，只是入栈顺序变成中、右、左：
class Solution {
public:
vector
总结
这一套标记法下来，前中后序的迭代代码终于不再各自为战了，只要改几行入栈顺序就能互相转换。但说实话，这个写法理解起来需要点时间，面试时直接手写也有一定难度。所以大家可以根据自己的习惯，选择一种自己最容易理解的递归或迭代法来掌握就好——不必强求统一。
其他语言版本
Ja va 迭代法前序遍历：
class Solution {
public List
Ja va 迭代法中序遍历：
class Solution {
public List
Ja va 迭代法后序遍历：
class Solution {
public List
Python 迭代法前序遍历：
class Solution:
def preorderTra versal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
st.append(node)
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result
Python 迭代法中序遍历：
class Solution:
def inorderTra versal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right:
st.append(node.right)
st.append(node)
st.append(None)
if node.left:
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
Python 迭代法后序遍历：
class Solution:
def postorderTra versal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
st.append(node)
st.append(None)
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result