二叉树中所有距离为 K 的结点 (All Nodes Distance K in Binary Tree)

1. 题目描述

题目背景： 在二叉树的算法题中，我们通常只能从父结点移动到子结点。但本题打破了这一限制，要求我们在树中进行“全向”搜索。这在 NOI 竞赛中属于典型的“树转图”或“父指针维护”类考题。

任务描述： 给定一棵拥有 $n$ 个结点的二叉树，一个目标结点 target（由其结点值表示），以及一个整数 $k$。 你需要找出所有与目标结点 target 距离为 $k$ 的结点，并返回这些结点值的列表。

输入格式：

1. 第一行包含三个整数 $n$、$T$ 和 $k$。其中 $n$ 为结点总数，$T$ 为目标结点的权值，$k$ 为要求的距离。
2. 接下来的 $n$ 行，每行包含三个整数 $v_i, l_i, r_i$：
   • $v_i$ 为当前结点的权值。
   • $l_i$ 为左孩子权值，若无左孩子则为 $-1$。
   • $r_i$ 为右孩子权值，若无右孩子则为 $-1$。
3. 保证所有结点的权值 $v_i$ 互不相同，范围在 $[0, n-1]$ 之间。

输出格式： 一行若干个整数，表示所有距离为 $k$ 的结点权值，按从小到大排序输出，整数之间用空格隔开。若不存在，则输出一个空行。

样例 1： 输入：

9 5 2
3 5 1
5 6 2
1 0 8
6 -1 -1
2 7 4
0 -1 -1
8 -1 -1
7 -1 -1
4 -1 -1

输出：

1 4 7

(解释：结点 5 是目标。距离为 2 的结点有：结点 7、结点 4 以及通过父结点 3 到达的结点 1。)

样例 2： 输入：

1 1 3
1 -1 -1

输出：

(输出空行)

数据范围限制：

• $1 \le n \le 500$
• $0 \le v_i < n$
• $0 \le k \le 1000$

2. 预备知识点

1. 二叉树的邻接表存储：将树结构转换为通用的无向图结构。
2. 父结点映射 (Parent Map)：在 DFS 过程中记录每个结点的父结点，使树具备向上回溯的能力。
3. 宽度优先搜索 (BFS)：从特定起点出发，按距离层层扩散，是解决“最短距离为 K”问题的最优选择。
4. 哈希表或访问标记数组：在搜索过程中记录已访问的结点，防止在父子结点间陷入无限循环。

3. 启发式思维引导

第一步：打破“向下”的思维定势

在普通的二叉树遍历中，我们只能从 root 走到 left 或 right。

• 思考：如果要找到目标结点 target 上方的结点，我们需要什么？
• 推论：我们需要知道每个结点的“爸爸”是谁。我们需要建立一个从子结点指向父结点的指针。

第二步：模型转换

如果我们将“左孩子”、“右孩子”和“父结点”都看作是与当前结点相连的“边”。

• 思考：这棵树现在变成了什么？
• 推论：一个每个结点度数最多为 3 的无向图。

第三步：搜索策略

从 target 结点出发，求距离为 $k$ 的所有结点。

• BFS 逻辑：
  1. 第 0 步：目标结点入队，标记访问。
  2. 第 1 步：取出队列中所有结点，将它们未访问的邻居（左、右、父）入队。
  3. 重复直到步数等于 $k$。
• DFS 逻辑：递归时携带 distance 参数，注意不要走回头路。

4. 算法流程图 (C++14 逻辑提示)

graph TD
    Start(开始) --> ReadData(读取输入并存储二叉树结构)
    ReadData --> BuildGraph(遍历树-利用 Map 或 数组存储每个结点的父结点)
    BuildGraph --> LocateTarget(在图中找到目标权值 T 对应的结点)
    
    LocateTarget --> BFS_Init(初始化队列 Q - 将 T 入队 - 标记 T 已访问)
    BFS_Init --> StepCheck{当前步数 step 等于 k 吗}
    
    StepCheck -- 否 --> QueueProcess(获取当前队列长度 sz)
    QueueProcess --> InnerLoop{循环 sz 次}
    
    InnerLoop -- 迭代 --> PopNode(弹出队首结点 u)
    PopNode --> CheckNeighbors(检查 u 的左孩子-右孩子-父结点)
    CheckNeighbors --> PushValid(若邻居存在且未访问-则入队并标记访问)
    PushValid --> InnerLoop
    
    InnerLoop -- 结束 --> StepInc(step 增加 1)
    StepInc --> StepCheck
    
    StepCheck -- 是 --> Collect(将当前队列中所有元素取出)
    Collect --> SortResult(对结果进行升序排序)
    SortResult --> Output(输出结果)
    Output --> End(结束)

5. 读题关键词总结

1. “距离为 K” (Distance K)：
   • NOI 经验：通常对应 BFS 或 DFS。在无权图中，BFS 寻找距离最直观。
2. “所有结点” (All Nodes)：
   • 指示：需要遍历所有可能的路径，不能只往下走。
3. “二叉树” (Binary Tree)：
   • 陷阱：不要被“二叉”限制了思路。当题目涉及向上回溯时，要立刻想到“增加父结点引用”或“转换为图”。
4. “权值唯一”：
   • 意义：可以直接用权值作为数组下标或哈希表的键，极大地简化了代码实现。

时间与空间复杂度分析：

• 时间复杂度：$O(n)$。建立父结点映射需要一次 $O(n)$ 遍历，BFS 搜索最多访问每个结点一次，也是 $O(n)$。排序结果耗时 $O(n \log n)$。总计 $O(n)$ 在 $n=500$ 下极快。
• 空间复杂度：$O(n)$。需要存储父结点映射、访问标记数组以及队列。

优化建议：

在 NOI 考场上，由于 $n$ 较小，可以使用 std::vector<int> adj[505] 直接建立无向图邻接表，将树完全看作图处理，代码量会更少且更不易出错。