迭代式二叉树后序遍历：某行代码为何必要？

先回顾维基百科中迭代后序遍历的核心伪代码片段（关键逻辑部分）：

stack ← empty stack
lastNodeVisited ← null
currentNode ← root
while currentNode ≠ null or stack is not empty:
    if currentNode ≠ null:
        push currentNode to stack
        currentNode ← currentNode.left
    else:
        peekNode ← top of stack
        if peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right:
            currentNode ← peekNode.right
        else:
            pop peekNode from stack
            visit peekNode
            lastNodeVisited ← peekNode

符合条件的二叉树示例 #

构造一棵只有右子链的二叉树：

A
     \
      B
       \
        C

即根节点A仅含右子节点B，B仅含右子节点C。

遍历过程拆解（重点看条件判定为False的时刻） #

1. 初始状态：stack为空，lastNodeVisited=null，currentNode=A
2. 将A压入栈，currentNode转向A.left（null）
3. 进入else分支，peekNode=A：
   • peekNode.right=B≠null，且lastNodeVisited=null≠B，因此currentNode=B
4. 将B压入栈，currentNode转向B.left（null）
5. 进入else分支，peekNode=B：
   • peekNode.right=C≠null，且lastNodeVisited=null≠C，因此currentNode=C
6. 将C压入栈，currentNode转向C.left（null）
7. 进入else分支，peekNode=C：
   • peekNode.right=null，弹出C并访问，lastNodeVisited=C
8. 此时栈不为空，peekNode=B：
   • peekNode.right=C≠null，但lastNodeVisited=C=peekNode.right，这里条件判定为False，不会将currentNode重新指向C（避免重复遍历），直接弹出B并访问，lastNodeVisited=B
9. 此时栈不为空，peekNode=A：
   • peekNode.right=B≠null，但lastNodeVisited=B=peekNode.right，条件再次判定为False，直接弹出A并访问，遍历结束

条件的必要性 #

如果去掉lastNodeVisited ≠ peekNode.right，当从C回到B时，会重复将currentNode设为C，导致无限循环——反复压入、弹出C，永远无法处理B和A。这个条件的核心作用是标记：当前节点的右子树已经完成遍历，无需再次处理，直接弹出当前节点即可。

内容的提问来源于stack exchange，提问作者adastra