解题思路

关键定义回顾

• 祖先：根到节点 u 路径上的所有节点（不含 u）。
• “中序前面的祖先”：把整棵树做一次中序遍历，沿序列从左到右走，记录在到达 u 之前出现的、同时又是 u 的祖先的那些节点，按出现顺序计数，第 k 个即答案；若不足 k 个返回 -1。

总体算法（一次建树 + 一次中序，O(n)）

1. 按层次序列建树

题目内容

在大规模语言模型 $(LLM$ $MOE)$ 架构中，每一层的 $MLP$ 模块中有若干个专家。用一颗二叉树把这些专家组织起来，二叉树的每个节点是一个专家。

现给定一个二叉树的根节点，以及两个整数 $u$ 和 $k$ 。任务是找出节点在二叉树中序遍历序列中的第 $k$ 个祖先节点的值。

一个节点的祖先节点是指从根节点到该节点路径上的所有节点(不包括该节点本身)。

这里，“第 $k$ 个祖先”指的是在中序遍历序列中，位于节点 $u$ 前面的所有祖先节点中的第 $k$ 个位置祖先节点。如果这样的祖先节点不存在，则返回 $-1$。

输入描述

输入将包含两行。

第一行是一个字符串，表示一棵二叉树：

<1>空节点用 '#' 表示;

<2>非空节点的值为整数;

<3>节点之间用一个空格分隔;

<4>树的层次遍历顺序给出比如，"$123$##$45$“ 表示根节点为 $1$ ，左子节点为 $2$ ，右子节点为 $3$ ; $2$ 没有子节点; $3$ 的左子节点为 $4$ ，右子节点为 $5$ 。

第二行包含两个整数 $u$ 和 $k$ ，分别表示目标节点的值和要查找的祖先节点的偏移量, 一个空格分隔这两个值。

输出描述

一个整数，表示在中序遍历序列中节点 $u$ 的第 $k$ 个祖先节点的值。如果不存在，则返回 $-1$ 。

样例1

输入

30 15 45 7 20 35 50 # # 18 # # 40
40 3

输出

-1

说明

二叉树结构如下：

中序遍历的顺序是：$7,15,18,20,30,35,40,45,50$。

节点 $u=40$ 。在中序遍历序列中，位于 $40$ 前面的节点有 $7,15,18,20,30,35$ 。

节点 $40$ 的祖先节点有 $30,45,35$ 。

在祖先节点中，在中序遍历序列中位于 $40$ 前面的有 $30,35$ 。

按照中序遍历顺序，其前面的祖先节点有： $30,35$。

第 $K=3$ 个祖先节点(即在 $40$ 前面第三个位置的祖先节点)不存在。

样例2

输入

10 5 15 2 7 12 18
7 1

输出

5

说明

二叉树结构如下：

中序遍历的顺序是：$2,5,7,10,12,15,18$ 。

节点 $u=7$ 。在中序遍历序列中，位于 $7$ 前面的节点有 $2,5$ 。

第 $k=1$ 个祖先(即在 $7$ 前面第二个位置的祖先)是 $5$ 。