5.3 综合题：非递归中序与树高

非递归中序维护栈：不断沿左链压栈；到空后弹出、访问，再转向右子树。循环条件是“当前指针非空或栈非空”，否则会在走到最左空指针时过早停止。

手工推演

对树 A 左 B、右 C，B 右 D：依次压 A、B；弹 B 访问，转 D，压 D；弹 D；再弹 A；最后压弹 C，得到 B-D-A-C。栈中始终保存尚未访问且左侧正在处理的祖先。

结构与代码

while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}cur=st.top();st.pop();visit(cur);cur=cur->right;}

迭代求高可用层序：每轮记录队列当前长度，处理完一层高度加一。

错解反馈

外层只写 while(cur) 会漏祖先；弹栈后忘转右子树造成死循环；用访问结点总数当空间复杂度，忽略栈最多只保存一条根到叶路径。

迁移练习

为空、单结点、左斜、只有右孩子四棵树分别实跑中序。独立验收：每一步写 cur、栈、输出，并说明循环不变量。