P3657.第2题-二叉树中序遍历的第k个祖先节点
题目内容
在大规模语言模型 (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 。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
