假设二叉树采用二叉链表存储结构，设计一个算法，求先序遍历序列中第 k 个结点的值。

[tag_link]

参考答案

按根、左、右的顺序递归访问，用 counter 记录已访问结点数；counter 首次等于 k 时返回当前结点并立即停止后续搜索。

伪代码

KthPreorder(T, k):
    if k < 1: return null
    counter = 0
    return Visit(T)

Visit(T):
    if T == null: return null
    counter = counter + 1
    if counter == k: return T
    found = Visit(T.left)
    if found != null: return found
    return Visit(T.right)

复杂度

找到前访问 k 个结点，时间 O(k)；最坏或 k 超出时为 O(n)。递归栈空间 O(h)。

边界条件

k<1 或 k 超出结点总数都返回 null；空树返回 null；k=1 返回根。

易错点

counter 必须按一次完整查询初始化，且找到后要短路返回，不能继续遍历并覆盖结果。

评分要点

体现先序次序；正确更新 counter；找到即返回；处理 k 非法或 k 超出；复杂度正确。