第 70 题
在二叉树中查找值为 x 的结点，编写非递归后序遍历算法打印该结点的所有祖先。假设值为 x 的结点至多一个。
[tag_link]
参考答案
用单栈和 lastVisited 模拟后序遍历。当目标结点准备出栈时，它的全部祖先仍按“根到双亲”的顺序保留在栈中，直接打印即可。
伪代码
PrintAncestors(root, x):
stack = empty; p = root; lastVisited = null
while p != null or not stack.empty():
while p != null:
stack.push(p)
p = p.left
top = stack.peek()
if top.right != null and lastVisited != top.right:
p = top.right
else:
stack.pop()
if top.data == x:
print stack from bottom to top // 栈中从底到顶
return true
lastVisited = top
return false
复杂度
最坏访问全部结点，时间 O(n)；栈空间 O(h)。打印本身另需 O(h) 时间。
边界条件
根就是 x 时打印空序列并返回 true；空树或 x 不存在返回 false；题设保证至多一个 x。
易错点
目标出栈后再打印会丢失祖先；应利用尚未弹出的栈内容，并且不要把目标自身打印为祖先。
评分要点
正确模拟非递归后序；识别右子树是否已访问；利用栈输出祖先；处理根和不存在。