迭代：用一个栈替代调用栈
递归之所以能遍历，全靠语言运行时的调用栈替我们记住「左子树走完后该回到哪个祖先」。把那个栈显式地搬到代码里——自己开一个数组当栈、用
while 循环驱动——就得到迭代写法。它和递归等价，但栈在堆上、深度可控，没有爆栈风险。三种序的循环骨架差别不小：前序最直接，中序要「一路向左压栈」，后序最难，得借一个 last 指针判断右子树是否已处理。
本页约定： 演示树是 BST，中序输出为升序。当前节点 curr / 栈顶用橙色描边;粉色描边标记关注的子节点（前序里刚压栈的左 / 右子）或后序的 last（最近一次访问的节点）；已访问节点填实心青色。下方栈横条：最左 = 栈底，最右 = 栈顶（下一个出栈）。
1 · 三种序为什么难度递增
前序最简单：弹栈即访问，再把右、左依次压栈（左后压、先出，故先处理）。栈里存的是「待处理的节点」。
中序居中：不能一弹栈就访问——得先把左边一条链全压进栈（curr 一路向左），弹栈时才轮到访问该节点，然后转向它的右子。栈里存的是「左子树已下潜、但自己还没访问的祖先」。
后序最难：一个节点要等左、右子树都处理完才能访问。光看栈顶分不清「右子树还没去」还是「右子树刚回来」，所以额外用一个 last 指针记住最近访问的节点：若栈顶的右子非空且不等于
last，说明右子树还没走，转过去；否则左右都处理过了，访问栈顶并弹出。单步观察 last 如何随访问推进。
后序还有一种等价简化写法。 注意「根 → 右 → 左」的前序，把输出整体逆序就是「左 → 右 → 根」的后序。于是可以套用最简单的前序骨架（压栈时改成先左后右），把结果反转即得后序——代价是要么用两个栈、要么往输出头部插入，都需要
O(n) 的额外空间存整个序列。本页上方演示的是不靠反转、用 last 指针的单栈真后序写法 (额外空间仍是 O(h))。
2 · 变通写法：跑一个前序，再把序列整体反转
把上面这个思路跑出来。用最简单的前序骨架（弹栈即记录），但压栈时改成先左后右——于是右子先出栈、先记录，得到的是「根 → 右 → 左」。遍历结束后把整条序列反转，就翻成「左 → 右 → 根」= 后序。单步到最后，看反转那几步如何把弹出序逐个翻过来；它和
last 指针的单栈真后序结果完全一致，差别只在这里额外用了 O(n) 空间存整条序列。