二叉树中距离为 K 的节点

记住「先给每个节点记住父亲、把树变无向图,再从 target 一圈圈 BFS 扩 k 层」,下面逐帧套它。

目标与距离：先看清局面:目标节点是 5(紫色高亮),我们要找所有离它恰好 2 步的节点。难点是 5 的上方(父亲 3 那一支)也算邻居,可树指针只能往下。

建父指针 ①：第一步建父指针。DFS 走一遍:5 和 1 的父亲都是 3,记进哈希表。有了父指针,5 就能反过来走到 3。

建父指针 ②：继续记:6、2 的父亲是 5,0、8 的父亲是 1,7、4 的父亲是 2;根 3 没有父亲。到此每条边都能双向走了,这棵树就成了一张无向图。

三个方向：有了父指针,从任何节点都能往「左孩子、右孩子、父亲」三个方向走。接下来从 target 5 出发做 BFS,像水波一圈圈扩散,第 2 圈就是答案。

BFS 起点 · 距离 0：把 target 5 放进队列,距离记 0,并标进 seen。5 自己离自己 0 步,从它开始一圈圈往外扩。

开始扩散 · 距离 0 这一圈：现在从距离 0 的这一圈 5(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 1 的下一圈。

扩散 · 看 5 的左孩子：从距离 0 的 5 看它的左孩子 6:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6。

扩散 · 看 5 的右孩子：从距离 0 的 5 看它的右孩子 2:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2。

扩散 · 看 5 的父亲：从距离 0 的 5 看它的父亲 3:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2、3。

距离 1 这一圈就位：距离 0 的节点全扩散完了。离 target 恰好 1 步的是 6、2、3。还没到 k=2,继续从它们往外扩。

开始扩散 · 距离 1 这一圈：现在从距离 1 的这一圈 6、2、3(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 2 的下一圈。

扩散 · 看 6 的父亲：从距离 1 的 6 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。

扩散 · 看 2 的左孩子：从距离 1 的 2 看它的左孩子 7:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7。

扩散 · 看 2 的右孩子：从距离 1 的 2 看它的右孩子 4:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4。

扩散 · 看 2 的父亲：从距离 1 的 2 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。

扩散 · 看 3 的左孩子：从距离 1 的 3 看它的左孩子 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。

扩散 · 看 3 的右孩子：从距离 1 的 3 看它的右孩子 1:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4、1。

距离 2 这一圈就位：距离 1 的节点全扩散完了。离 target 恰好 2 步的是 7、4、1。正好扩满 2 圈,这一圈就是要找的答案。

命中 · 距离 = k：扩满 2 圈,队列里剩下的 7、4、1(紫色)就是距 target 5 恰好 2 步的全部节点,答案 [7, 4, 1]。7、4 在 5 下方经过 2,1 在上方经过 3,都是两步。

回顾：回头看整趟:先 DFS 给每个节点记父亲、把树变成无向图,再从 target 一圈圈 BFS、靠 seen 防回头,扩满 k 圈就拿到答案。每个节点最多进出队一次,时间 O(n)。

边界:k=0 只返回自己;k 过大返回空;叶子靠父指针照样扩。

两个追问:也可纯 DFS(更绕);返回节点/大 k 都不改主逻辑。