解题思路

关键定义回顾

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

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

1. 按层次序列建树

   • 输入是层次遍历（BFS）序列，空节点为 #。

   • 用队列逐层挂接左右孩子；同时维护：

     • parent：节点 → 父节点 指针（便于之后找祖先）；
     • val2node：值 → 节点 指针（便于定位 u）。

   说明：题目通常默认结点值唯一，若不唯一则需用“节点身份”而非“值”来定位；本题按样例与常规题型 默认值唯一。

2. 若不存在值为 u 的节点：直接输出 -1。

3. 得到祖先集合

   • 从 val2node[u] 沿 parent 回溯到根，放入一个 anc 哈希集合，表示 u 的全部祖先。

4. 一次中序遍历并计数

   • 进行中序遍历（左—根—右），维护一个计数器 cnt。

   • 每访问到一个节点 x：

     • 若 x == u，停止遍历：若 cnt >= k 则答案在“前面的祖先”中第 k 个；反之 -1。
     • 若 x 在 anc 集合中，则 cnt += 1，当 cnt == k 时把当前节点值记为 ans_k（因为之后还可能没到 u，先保存，等遇到 u 再输出）。

   • 结束条件：遍历到 u 即可（不用遍历全树）。

该策略直接把“在中序序列里位于 u 之前且为祖先”的定义转化为一次遍历的在线计数，无需额外数组与二分。

复杂度分析

• 设节点数为 n。
• 建树：O(n)；构造 parent/val2node：O(n)；
• 中序遍历直到遇到 u：最坏 O(n)；
• 总时间复杂度：O(n)；空间复杂度：O(n)（队列、映射、祖先集合与递归/显式栈）。

代码实现

Python 实现

import sys
from collections import deque

class Node:
    def __init__(self, v):
        self.v = v
        self.l = None
        self.r = None

def build_tree(tokens):
    # 空或首元素为# => 空树
    if not tokens or tokens[0] == '#':
        return None, {}, {}
    it = 0
    root = Node(int(tokens[it]))
    it += 1
    q = deque([root])
    parent = {root: None}
    val2node = {root.v: root}
    # 逐个为队首节点挂接左右孩子
    while q and it < len(tokens):
        cur = q.popleft()
        # 左孩子
        if it < len(tokens):
            t = tokens[it]; it += 1
            if t != '#':
                left = Node(int(t))
                cur.l = left
                parent[left] = cur
                val2node[left.v] = left
                q.append(left)
        # 右孩子
        if it < len(tokens):
            t = tokens[it]; it += 1
            if t != '#':
                right = Node(int(t))
                cur.r = right
                parent[right] = cur
                val2node[right.v] = right
                q.append(right)
    return root, parent, val2node

def kth_ancestor_in_inorder_before_u(root, parent, val2node, u, k):
    # u不存在
    if u not in val2node:
        return -1
    u_node = val2node[u]
    # 收集u的全部祖先到集合
    anc = set()
    p = parent.get(u_node)
    while p is not None:
        anc.add(p)
        p = parent.get(p)
    # 中序遍历（显式栈），计数祖先并在遇到u时判定
    stack = []
    cur = root
    cnt = 0
    ans_k = None  # 提前保存第k个祖先的值
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.l
        cur = stack.pop()
        # 访问cur
        if cur is u_node:
            # 到达u，返回结果（若此前出现了第k个祖先）
            return ans_k if cnt >= k else -1
        if cur in anc:
            cnt += 1
            if cnt == k:
                ans_k = cur.v
        # 继续右子树
        cur = cur.r
    return -1

def main():
    data = sys.stdin.read().strip().splitlines()
    if len(data) < 2:
        print(-1)
        return
    tokens = data[0].strip().split()
    u, k = map(int, data[1].strip().split())
    root, parent, val2node = build_tree(tokens)
    ans = kth_ancestor_in_inorder_before_u(root, parent, val2node, u, k)
    print(ans)

if __name__ == "__main__":
    main()

Java 实现

import java.io.*;
import java.util.*;

public class Main {

    static class Node {
        int v;
        Node l, r;
        Node(int v) { this.v = v; }
    }

    static class BuildResult {
        Node root;
        Map<Node, Node> parent;
        Map<Integer, Node> val2node;
        BuildResult(Node root, Map<Node, Node> parent, Map<Integer, Node> val2node) {
            this.root = root; this.parent = parent; this.val2node = val2node;
        }
    }

    // 构建二叉树（层次遍历）
    static BuildResult buildTree(String[] tok) {
        if (tok.length == 0 || tok[0].equals("#")) {
            return new BuildResult(null, new HashMap<>(), new HashMap<>());
        }
        int it = 0;
        Node root = new Node(Integer.parseInt(tok[it++]));
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        Map<Node, Node> parent = new HashMap<>();
        parent.put(root, null);
        Map<Integer, Node> val2node = new HashMap<>();
        val2node.put(root.v, root);

        while (!q.isEmpty() && it < tok.length) {
            Node cur = q.poll();
            // 左孩子
            if (it < tok.length) {
                String t = tok[it++];
                if (!t.equals("#")) {
                    Node left = new Node(Integer.parseInt(t));
                    cur.l = left;
                    parent.put(left, cur);
                    val2node.put(left.v, left);
                    q.add(left);
                }
            }
            // 右孩子
            if (it < tok.length) {
                String t = tok[it++];
                if (!t.equals("#")) {
                    Node right = new Node(Integer.parseInt(t));
                    cur.r = right;
                    parent.put(right, cur);
                    val2node.put(right.v, right);
                    q.add(right);
                }
            }
        }
        return new BuildResult(root, parent, val2node);
    }

    // 在中序序列中，位于u之前的祖先的第k个
    static int kthAncestorInorderBeforeU(Node root, Map<Node, Node> parent,
                                         Map<Integer, Node> val2node, int u, int k) {
        Node uNode = val2node.get(u);
        if (uNode == null) return -1;

        // 祖先集合
        HashSet<Node> anc = new HashSet<>();
        Node p = parent.get(uNode);
        while (p != null) {
            anc.add(p);
            p = parent.get(p);
        }

        // 显式栈做中序
        Deque<Node> st = new ArrayDeque<>();
        Node cur = root;
        int cnt = 0;
        Integer ansK = null;
        while (!st.isEmpty() || cur != null) {
            while (cur != null) {
                st.push(cur);
                cur = cur.l;
            }
            cur = st.pop();
            // 访问cur
            if (cur == uNode) {
                return (cnt >= k) ? ansK : -1;
            }
            if (anc.contains(cur)) {
                cnt++;
                if (cnt == k) ansK = cur.v;
            }
            cur = cur.r;
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
        String line1 = br.readLine();
        String line2 = br.readLine();
        if (line1 == null || line2 == null) {
            System.out.println(-1);
            return;
        }
        String[] tok = line1.trim().split("\\s+");
        String[] uv = line2.trim().split("\\s+");
        int u = Integer.parseInt(uv[0]);
        int k = Integer.parseInt(uv[1]);

        BuildResult res = buildTree(tok);
        int ans = kthAncestorInorderBeforeU(res.root, res.parent, res.val2node, u, k);
        System.out.println(ans);
    }
}

C++ 实现

// 按层序建树 + 中序遍历计数
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int v;
    Node *l, *r;
    Node(int _v): v(_v), l(NULL), r(NULL) {}
};

struct BuildResult {
    Node* root;
    unordered_map<Node*, Node*> parent;
    unordered_map<int, Node*> val2node;
};

BuildResult buildTree(const vector<string>& tok) {
    BuildResult res; res.root = NULL;
    if (tok.empty() || tok[0] == "#") return res;
    int it = 0;
    res.root = new Node(stoi(tok[it++]));
    queue<Node*> q;
    q.push(res.root);
    res.parent[res.root] = NULL;
    res.val2node[res.root->v] = res.root;

    while (!q.empty() && it < (int)tok.size()) {
        Node* cur = q.front(); q.pop();
        // 左孩子
        if (it < (int)tok.size()) {
            string t = tok[it++]; 
            if (t != "#") {
                Node* left = new Node(stoi(t));
                cur->l = left;
                res.parent[left] = cur;
                res.val2node[left->v] = left;
                q.push(left);
            }
        }
        // 右孩子
        if (it < (int)tok.size()) {
            string t = tok[it++];
            if (t != "#") {
                Node* right = new Node(stoi(t));
                cur->r = right;
                res.parent[right] = cur;
                res.val2node[right->v] = right;
                q.push(right);
            }
        }
    }
    return res;
}

int kthAncestorInorderBeforeU(Node* root,
                              unordered_map<Node*, Node*>& parent,
                              unordered_map<int, Node*>& val2node,
                              int u, int k) {
    if (!val2node.count(u)) return -1;
    Node* uNode = val2node[u];
    // 祖先集合
    unordered_set<Node*> anc;
    Node* p = parent[uNode];
    while (p) { anc.insert(p); p = parent[p]; }

    // 显式栈中序
    stack<Node*> st;
    Node* cur = root;
    int cnt = 0;
    int ansK = INT_MIN; // 记第k个祖先值
    bool hasAns = false;

    while (!st.empty() || cur) {
        while (cur) { st.push(cur); cur = cur->l; }
        cur = st.top(); st.pop();
        // 访问cur
        if (cur == uNode) {
            return (cnt >= k) ? ansK : -1;
        }
        if (anc.count(cur)) {
            cnt++;
            if (cnt == k) { ansK = cur->v; hasAns = true; }
        }
        cur = cur->r;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line1, line2;
    if (!getline(cin, line1)) { cout << -1 << "\n"; return 0; }
    if (!getline(cin, line2)) { cout << -1 << "\n"; return 0; }
    // 分割
    stringstream ss1(line1), ss2(line2);
    vector<string> tok;
    string t;
    while (ss1 >> t) tok.push_back(t);
    int u, k;
    ss2 >> u >> k;

    BuildResult res = buildTree(tok);
    int ans = kthAncestorInorderBeforeU(res.root, res.parent, res.val2node, u, k);
    cout << ans << "\n";
    return 0;
}

题目内容

在大规模语言模型 $(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$ 。