设计一个算法，将二叉树的叶结点按从左到右的顺序连成单链表，表头指针为 head，并用叶结点的 right 指针域保存链表后继。

[tag_link]

参考答案

按先左后右的 DFS 次序遇到叶结点。head 记录首叶，tail 记录末叶；新叶到来时令 tail.right 指向它，结束后令最后一个叶结点的 right 为空。

伪代码

LinkLeaves(T, ref head, ref tail):
    if T == null: return
    if T.left == null and T.right == null:
        if head == null: head = T
        else: tail.right = T
        tail = T
        return
    LinkLeaves(T.left, head, tail)
    LinkLeaves(T.right, head, tail)

head = null; tail = null
LinkLeaves(root, head, tail)
if tail != null: tail.right = null

复杂度

每个结点访问一次，时间 O(n)；递归栈空间 O(h)，链表复用原指针，不另占结点空间。

边界条件

空树得到 head=null；单结点树中 head=tail=root 且 right=null；最后必须封尾。该做法会改写叶结点的 right 指针。

易错点

必须按左到右遍历；不要在处理完左子树前沿已改写的叶 right 再次递归，也不要忘记保存 tail 和封尾。

评分要点

正确识别叶结点；head/tail 初始化；按先左后右连接；tail.right = T；说明会破坏原树叶结点的 right 域。