第 64 题
假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
[tag_link]
参考答案
使用队列层序遍历。last 指向当前层最后一个结点，nextLast 记录下一层最后入队的结点；弹出 last 时层数 level 加 1。
伪代码
Height(T):
if T == null: return 0
Q.enqueue(T); level = 0; last = T; nextLast = null
while not Q.empty():
p = Q.dequeue()
if p.left != null: Q.enqueue(p.left); nextLast = p.left
if p.right != null: Q.enqueue(p.right); nextLast = p.right
if p == last:
level = level + 1
last = nextLast
return level
复杂度
每个结点入队、出队一次，时间 O(n)；队列最多保存一层结点，空间 O(w)，w 为最大宽度。
边界条件
空树高度返回 0；单结点树返回 1。nextLast 只在孩子入队时更新，最后一层没有孩子也不影响循环结束。
易错点
不能用队列长度的瞬时值直接当高度；更新 last 必须发生在当前层最后结点处理完之后。
评分要点
给出队列；正确维护 level、last、nextLast；处理空树；写出 O(n) 与 O(w)。