二叉树中如何找距离目标节点 K 的所有节点？为什么要把树看成无向图？

简化版

找距离目标节点 K 的节点时，路径可能向下走到子节点，也可能向上走到父节点。因此常先建立 parent 映射，把二叉树看成无向图，再从 target 做 BFS 扩展 K 层。

详细版

普通二叉树节点只有左右孩子指针，不能直接往父节点走。但距离 K 的路径不限制方向。

做法：

DFS 遍历整棵树，记录 parent[child] = node。
从 target 开始 BFS。
每个节点的邻居是 left、right、parent。
用 visited 防止从父子之间来回走。
BFS 扩展到第 K 层，当前队列里的节点就是答案。

时间复杂度 O(n)，空间 O(n)。关键是把树的有向父子关系补成可双向行走的图。

完整版教学

一、为什么只向下 DFS 不够

如果目标节点在左子树，距离 K 的节点可能在它的子树里，也可能经过父节点走到兄弟子树。

      1
     / \
    2   3
   /
  4
target = 2, K = 2

距离 2 的节点包括 3，路径是 2 -> 1 -> 3。这条路径需要先向上到父节点，再向下到兄弟节点。只沿 left/right 向下走找不到。

二、为什么要建立 parent 映射

普通二叉树节点没有 parent 指针。为了从 target 向上走，需要提前记录每个节点的父节点。

function buildParent(node, parent) {
  if (!node) return;
  parentMap.set(node, parent);
  buildParent(node.left, node);
  buildParent(node.right, node);
}

这样每个节点的邻居就从两个孩子扩展成最多三个方向：left、right、parent。

三、为什么要看成无向图

树本身也是一种无环连通图。补上 parent 后，任意相邻父子节点都可以双向走。

node 的邻居：
left child
right child
parent

从 target 出发找距离 K，其实就是图上的 BFS 最短距离问题。BFS 每扩展一层，距离就加 1；扩展 K 层后正好得到距离 K 的所有节点。

四、visited 为什么必须有

补上 parent 后，边变成双向。如果不记录 visited，会在父子之间来回走。

2 -> 1 -> 2 -> 1 ...

visited 保证每个节点只入队一次。树没有环，但当你把父子边当成双向边后，来回走就是图搜索中的重复访问问题。

五、BFS 层数怎么控制

可以把队列按层处理。初始 target 是第 0 层，每扩展一轮距离加 1。当距离等于 K 时，队列中所有节点就是答案。

dist=0: target
dist=1: target 的邻居
dist=2: 邻居的未访问邻居

如果 K=0，答案就是 target 本身。这个边界要提前处理或让 BFS 自然支持。

六、复杂度和变体

建立 parent 映射 O(n)，BFS 最坏访问所有节点 O(n)，总时间 O(n)，空间 O(n)。如果节点本身有 parent 指针，就可以省掉建表阶段。

方案	思路	复杂度特点
parentMap + BFS	先补父指针，再从 target 扩散	直观，时间 O(n)、空间 O(n)
递归返回距离	自底向上找 target 并处理兄弟子树	空间可少一些，但逻辑更绕
节点自带 parent	直接把树当无向图 BFS	省掉建 parentMap

记忆钩子：距离 K 不是“往下 K 层”，而是“从 target 走 K 条边”；能往父节点走后，树就变成无向图 BFS。

七、常见误区与追问

误区：距离 K 只需要搜索 target 的子树。 目标节点的父方向和兄弟子树也可能有答案。
误区：树没有环，所以 BFS 不需要 visited。 加了 parent 后会在父子之间来回走，必须 visited。
误区：K=0 返回空。 K=0 时距离目标 0 的节点就是目标节点。
追问：没有 target 引用只有 target 值怎么办？ 先遍历找到目标节点，再 BFS。
追问：能不用 parentMap 吗？ 可以递归返回距离并处理兄弟子树，但逻辑更复杂；图化 BFS 更直观。

八、加强记忆

这题的关键转换是“树题变图题”。只向下不是距离，能沿父子边双向走才是距离。先建 parent，再从 target 做 BFS，扩展 K 层即可；visited 是防止双向边反复走的保险。

简化版

详细版