企业官网建设流程全解析

看到 LeetCode 863 这道题，我第一反应是：二叉树里找距离 target 为 K 的节点，不就是从 target 出发 BFS 扩散 K 层吗？但真正上手写代码的时候才发现不对劲——树的节点只有left和right两个指针，你站在 target 上只能往两个孩子走，根本不知道父节点是谁，更没办法“往上”走。这道题难倒不少人的地方，恰恰不是 BFS 本身，而是怎么把一棵“只能从上往下走”的树，变成一张能任意回头的图。

题目本身很简洁：给定一棵二叉树根节点root、一个目标节点target、一个整数K，返回所有与target距离恰好为K的节点值。这里的“距离”指的是边的数量，比如K=0时答案就是[target.val]。适合刷树题卡在“遍历方向单一”这个瓶颈上的人，也适合准备面试想把图论建模思路捋清楚的人。我下面会讲两条完全不同的解法路径：一条是建父指针再做 BFS，另一条是不建映射、靠递归栈回溯。两条路我都会给出完整代码和实测中容易翻车的细节。

1. 题目在考什么：二叉树没有“向上走的指针”

1.1 题干里的关键约定

先把题意翻译成最容易理解的形式：root给一棵二叉树，target是这棵树里的某个节点，K是一个非负整数。需要返回一个数组，里面是所有和target相距K条边的节点值。题目有两个不起眼但很重要的约定：

• 树中所有节点的值都是唯一的，所以返回的是具体数值也不会混淆；
• 返回顺序是任意的，不需要按照某种排序输出。

举个例子，一棵树长这样：

3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4

假如target = 5，K = 2，那么距离 5 两步的节点有哪些？从 5 往下走两步：5 -> 2 -> 7、5 -> 2 -> 4；从 5 往上走两步：5 -> 3 -> 1。所以答案是[7, 4, 1]，顺序可以颠倒。

这个例子很经典，因为它同时覆盖了“往下走”和“往上走”两个方向。如果你只用从根出发的 DFS 或 BFS，根本覆盖不到1这个答案，因为 1 是 target 的叔叔，它既不在 target 的子树里，也不是从根一路向下就能直接碰到的邻居。

1.2 为什么常规 DFS 搞不定这个距离

很多人在做这道题之前，已经刷了不少二叉树题目，比如最近的公共祖先、层序遍历、路径总和等等。这些题有一个共同点：遍历都是从根节点开始，沿着left和right一路向下走。也就是说，树的每条边其实是一条单向边：父节点 -> 子节点。

但863问的是从 target 出发向外扩 K 步。target 可能在树中任意位置，K 步之内可能覆盖到它的祖先、它祖先的另一棵子树、它自己的子树。如果只沿left/right递归，那 target 的祖父节点根本不会被访问到，更别说祖父的另一侧分支。

用图论的语言来描述就是：一棵二叉树天然是一张有向图，但这个方向是“一向向下”的。我们现在要在一个局部范围里做“无向扩散”，就必须把反向边补上。谁是指向父亲的边？在 C++ 里没有现成的字段，那就需要自己记录一份父指针映射。这是整道题最重要的转化，比 BFS 本身高级得多。

2. 建模思路：把树变成一张可以回头的无向图

2.1 用哈希表给每个节点挂一个父指针

既然树本身没有向上走的通道，那我们就手动建一个哈希表parent，键是当前节点指针，值是该节点的父节点指针。遍历一次整棵树，把每个非空节点的父节点都记录清楚。这样任何一个节点在逻辑上就有了三个邻居：

• node->left
• node->right
• parent[node]

前两个是本来就有的，第三个是我们补出来的反向边。有了这三个方向，从任何一个节点出发，都能像在无向图里一样自由探索。

这里有个细节需要注意：根节点没有父节点，所以parent[root]要为nullptr。这样在 BFS 遍历邻居的时候，判断if (nxt)就能把根节点“没有爸爸”这个情况自然过滤掉，不会出现空指针访问。

2.2 为什么不直接建邻接表

你可能想问：既然要当图处理，为什么不干脆建一个邻接表unordered_map<TreeNode*, vector<TreeNode*>>，把左右孩子和父节点都塞进一个 vector？这样做在技术上完全可行，而且对于“多叉树”或“树上任意两个节点间距离”这类问题来说，邻接表会更通用。

但对于这道题，邻接表有点重。二叉树每个节点的出边固定就是三条：左、右、父。用vector存储意味着每个节点都要维护一个动态数组，建图的时候要先创建 vector，再逐个push_back；遍历的时候又要在循环里取neighbor。父指针哈希表则完全复用现有的left、right两个指针，只是额外补一条反向边。代码更轻，遍历逻辑也几乎不用包装。

我自己的经验是：二叉树题里“补父指针”这个操作，比“转邻接表”更贴合面试官的预期。因为它显示你理解树的递归性质，同时只用了最小的额外空间就把图化问题解决了。

2.3 一次 DFS 就能完成建表

建父指针的过程非常短，就是一次标准的先序 DFS：

void buildParent(TreeNode* node, TreeNode* par) { if (!node) return; parent[node] = par; buildParent(node->left, node); buildParent(node->right, node); }

调用方式：

buildParent(root, nullptr);

这个函数会把根节点的父指针设为nullptr，然后对左右子树递归，把每个孩子的父指针都指向当前节点。时间复杂度 O(n)，空间复杂度 O(h)，h是树高。实际存储父指针的哈希表要额外 O(n) 空间，但建表的过程本身不需要额外容器来收集路径。

到这里，建模完成。接下来就可以从 target 出发做图上的扩散搜索了。

3. 从 target 出发一层一层往外扩：BFS 实现

3.1 完整可运行的 BFS 代码

建好父指针映射之后，从 target 出发的 BFS 就是标准的图上按层遍历。先把根节点记录下来，再一层一层扩展，扩展到第 K 层时，队列里剩下的所有节点就是答案。

class Solution { private: unordered_map<TreeNode*, TreeNode*> parent; void buildParent(TreeNode* node, TreeNode* par) { if (!node) return; parent[node] = par; buildParent(node->left, node); buildParent(node->right, node); } public: vector<int> distanceK(TreeNode* root, TreeNode* target, int k) { buildParent(root, nullptr); unordered_set<TreeNode*> visited; queue<TreeNode*> q; q.push(target); visited.insert(target); int dist = 0; while (!q.empty()) { int sz = q.size(); if (dist == k) { vector<int> ans; while (!q.empty()) { ans.push_back(q.front()->val); q.pop(); } return ans; } for (int i = 0; i < sz; ++i) { TreeNode* cur = q.front(); q.pop(); TreeNode* nextNodes[3] = {cur->left, cur->right, parent[cur]}; for (TreeNode* nxt : nextNodes) { if (nxt && visited.find(nxt) == visited.end()) { visited.insert(nxt); q.push(nxt); } } } ++dist; } return {}; } };

这段代码有几点值得细品。

第一，dist从 0 开始，表示当前队列里的节点距离 target 是几步。一开始队列里只有 target，此时dist == 0。如果k == 0，第一轮while就会命中dist == k的分支，直接返回[target.val]，根本不会扩展邻居。这个边界是天然成立的，不需要额外写if (k == 0)的特判。

第二，nextNodes[3]把三个邻居统一放到一个小数组里统一处理。在实际建图的时候，parent[cur]对根节点是nullptr，cur->left或cur->right也可能是nullptr。统一用if (nxt)过滤，简洁又安全。

第三，visited必不可少。因为这是一张无向图——你用parent指针从孩子走到父亲，后面扩展父亲时又会通过left回到同一个孩子。如果没有visited，队列会无限膨胀，程序直接超时或死循环。

3.2 visited 去重和图化后的本质变化

我见过不少人第一次写完 BFS 后，本地一跑就卡死，或者内存占用飙升，问题几乎都出在漏写visited。

你可以这样想：树本来没有环，但一旦补上父指针，原来的一条无向边就变成了两条方向相反的边。孩子通过left访问父亲，父亲通过child指针访问孩子，这两个方向交替进行就构成环。而 BFS 遍历必须保证“每个节点只进入队列一次”，否则没法保证距离递增，也会出现重复入队。

在二叉树原本的向下遍历里，因为节点不可能向上走，天然不会回头，所以不需要visited。但做了图化处理之后，visited就不再是可选项，而是必经之路。

也可以用另一种方式替代visited：在递归/遍历时记录from来源方向。下面这段 DFS 版代码和 BFS 思路等价，但用from参数代替了visited：

class Solution { private: unordered_map<TreeNode*, TreeNode*> parent; vector<int> ans; void buildParent(TreeNode* node, TreeNode* par) { if (!node) return; parent[node] = par; buildParent(node->left, node); buildParent(node->right, node); } void dfs(TreeNode* node, TreeNode* from, int depth, int k) { if (!node) return; if (depth == k) { ans.push_back(node->val); return; } if (node->left != from) dfs(node->left, node, depth + 1, k); if (node->right != from) dfs(node->right, node, depth + 1, k); if (parent[node] != from) dfs(parent[node], node, depth + 1, k); } public: vector<int> distanceK(TreeNode* root, TreeNode* target, int k) { buildParent(root, nullptr); dfs(target, nullptr, 0, k); return ans; } };

注意，这段代码里node->left != from的判断就避免了回退到刚刚来的节点。因为图上三条边中，至少有一条边指向来路，剩下的方向才值得继续走。它的效果和visited一样，只是实现方式更轻。实际用哪种取决于习惯，我更喜欢visited版本，因为视觉上更接近常见的 BFS 模板，排查问题的时候也更容易看出哪些节点被访问过。

3.3 为什么第 K 层就是答案

BFS 能给出答案的核心原因是队列的逐层扩展性质：第一轮扩展的是距离 target 为 1 的节点，第二轮扩展的是距离为 2 的节点，依此类推。当某一轮开始之前队列里全是距离 dist 的节点时，我们就可以断言这些节点满足条件。

这个结论可以这样验证：假设 target 到某个节点 X 的最短路径长度是 d。BFS 扩展过程就是从 target 出发，一次走一条边，所有经过 d 步能到达的节点都会在第 d 轮被放入队列。由于图的边权都是 1，所以第一次访问到 X 时用的就是最短距离。因此第 K 轮时队列里的每个节点，距离都是 K。

4. 不建映射也能做：沿祖先回溯的递归解法

4.1 利用递归栈代替哈希表

建父指针+BFS 是多数人能直接想到的方案。不过这道题还有一条更巧妙的路径，代码可以更短，而且完全不需要哈希表。关键想法是：既然递归过程中天然保留着从根到当前节点的路径信息，那么当递归到 target 时，函数逐层返回的过程，其实就是从 target 一步一步回溯到祖先的过程。

结构上可以这样设计：写一个dfs(root, target, k)，它返回“target 在以 root 为根的子树中离 root 的深度”，如果 target 不在这个子树里就返回 -1。当root == target时，深度为 0；当 target 在左子树或右子树时，当前层的深度就是子树返回深度 +1。

每次回溯到祖先节点时，我们自然会得到一个关键信息：从当前祖先到 target，已经走了几步。那么剩下的步数，就应该往当前祖先的另一侧子树里继续找。比如 target 在左子树，已知离当前节点还有leftDist步，那从当前节点到 target 就是leftDist + 1步。如果K = leftDist + 1，当前节点本身就是答案；否则需要在右子树里再往下走K - leftDist - 2步，因为还要减去“从当前节点走到右孩子”这一步。

4.2 完整实现与执行逻辑

class Solution { private: vector<int> ans; void collect(TreeNode* root, int d) { if (!root || d < 0) return; if (d == 0) { ans.push_back(root->val); return; } collect(root->left, d - 1); collect(root->right, d - 1); } int dfs(TreeNode* root, TreeNode* target, int k) { if (!root) return -1; if (root == target) { collect(root, k); return 0; } int leftDist = dfs(root->left, target, k); if (leftDist != -1) { if (leftDist + 1 == k) { ans.push_back(root->val); } else { collect(root->right, k - leftDist - 2); } return leftDist + 1; } int rightDist = dfs(root->right, target, k); if (rightDist != -1) { if (rightDist + 1 == k) { ans.push_back(root->val); } else { collect(root->left, k - rightDist - 2); } return rightDist + 1; } return -1; } public: vector<int> distanceK(TreeNode* root, TreeNode* target, int k) { dfs(root, target, k); return ans; } };

这段代码初看容易懵的点是collect(root->right, k - leftDist - 2)里的那个-2。这里做一个拆解：

• leftDist是 target 在左子树中的深度，也就是从root->left到 target 需要走leftDist步；
• 那么从root到 target，需要先走一步到root->left，再走leftDist步，所以总距离是leftDist + 1；
• 现在想从root出发向右子树走，第一步先到root->right，这一步也算在路径里；
• 因此右子树里还差K - (leftDist + 1) - 1 = K - leftDist - 2步。

如果K - leftDist - 2是个负数，说明这个方向根本走不到 K 步，collect里的d < 0判断会直接跳过，啥也不加，逻辑上是正确的。

collect这个名字的意思是“向下收集”：从某个祖先节点出发，向它的子树方向里收集距离 d 的节点。它只负责向下走，因为从 target 向上的路径，已经在递归回溯时由每一层的祖先分支处理过了。

举个小例子验证。一棵树：

1 / \ 2 3 \ 4

target = 4，K = 1。先进入dfs(1)，走左子树dfs(2)，再走右子树发现dfs(2->right) = dfs(4)。在 4 这里命中root == target，于是collect(4, 1)在 4 的子树里找距离 1 的节点，4 没有孩子，所以什么都没加，返回 0。回到dfs(2)，rightDist = 0，判断0 + 1 == 1，把 2 加入答案。最后返回 1 给dfs(1)，1 + 1 != 1，于是走collect(1->right, 1 - 1 - 2)，即collect(3, -2)，直接跳过。答案正好是[2]。

4.3 回溯时 collect 为什么只能往下走

这是递归回溯解法里最容易被追问的问题。如果你在collect里也往父方向走，会发生什么？首先，父方向本来就已经在回溯路径里被检查过了。比如上面的例子里，当dfs(2)知道 target 在右子树后，它已经处理了“当前节点 2 是不是答案”以及“左子树里有没有答案”这两个方向。如果collect还往上走，就会重新访问已经处理过的父节点，造成重复和潜在环。其次，collect的调用方只在“某个祖先发现自己距离 target 已知”时才调用它，这时候向上的路径已经由调用者和它之上的层负责，collect只需要专心处理“兄弟子树”和“后代子树”。

你可以把collect理解成一个单向收尾函数，递归回溯函数则负责在 target 到根的整条链上做方向切换。两者配合，就把三个方向完全覆盖了。

5. 边界条件与几个容易翻车的实测点

5.1 K = 0 时两种写法的表现

K=0意味着返回[target.val]。BFS 版会在进入while后第一轮就命中dist == k，所以队列里的 target 会被原样返回。递归版在root == target时调用collect(root, 0)，它会把 target 自身加入答案。所以两种写法都不需要额外的if (k == 0)特判。

但有一个细节要注意：面试时很多同学会习惯性地先写if (k == 0) return {target->val};，然后再进入 BFS。这样虽然不是错误，却容易让后续的扩展逻辑失去“天然支持 K=0”这个特性。我个人觉得没必要加特判，把代码写成泛化统一的版本，边界反而清晰。

5.2 target 是叶子节点的情况

叶子节点没有孩子，所以 BFS 里nextNodes数组的left和right都是nullptr，唯一有效方向就是parent[cur]。如果 K 是 1，答案就是它的父节点；如果 K 更大，就从父节点继续向上，同时进入父节点的另一侧子树。

这里有个容易踩的坑：当 BFS 走到根节点时，parent[root]是nullptr，如果不加过滤就把nullptr入队，后面取q.front()->val直接内存错误。我在本地调试时见过很多次这种崩溃。解决办法就是在入队前统一做if (nxt && visited.find(nxt) == visited.end())的判断。

5.3 K 超过树高或者答案不存在

如果整棵树很小，而 K 很大，BFS 的队列在某一次扩展后变空，while循环退出，最后返回{}。递归版也一样：collect里的d < 0会让所有分支都跳过，最终答案数组为空。这个行为不需要额外处理，唯一要注意的是别把“空答案”误当成“程序 bug”。

5.4 节点值唯一条件下的去重策略

题目声明了节点值唯一，所以你确实可以用unordered_set<int>来去重。但从写代码的角度，我建议仍然用TreeNode*指针做visited的键，原因有两条：

• 指针是内存地址，天然唯一，即使树里出现相同值也不会误判；
• 如果面试官把题目改成多叉树或者允许值重复，set<int>版本立刻出错，而指针版本只需要改邻居生成逻辑，核心不变。

用指针还有一个隐性好处：判断一个节点是否访问过，不需要額外做一次“值到节点”的映射查找，处理 null 也更直观。

5.5 答案顺序与排序问题

题目明确说“可以按任意顺序返回”。这意味着不需要对结果排序，直接按 BFS 层序或者递归遍历顺序返回就行。不过如果你要输出的结果需要和示例顺序一致，或者面试官口头要求升序输出，就在返回前对ans做一次sort。这个操作不影响核心逻辑，只影响展示。

6. 复杂度对比与同类题目的延伸思考

6.1 两种写法的时间/空间对比

时间上两者都是 O(n)，因为每个节点都只会被访问常数次。空间上 BFS 多了一个哈希表和一个 visited，所以整体空间是 O(n)；递归回溯省去了哈希表，看起来更省，但在退化成链的树里，递归栈深度也会到 O(n)，所以最坏情况下并没有本质优势。

6.2 从 863 看一类“扩散距离”的题目

这道题刷完，最大的收获不是记住“二叉树建父指针”这个技巧，而是建立一种意识：当题目要求在树上按“距离”做搜索时，往往需要先把树当成无向图来处理。父指针是补边的手段，visited是防止回头的手段，BFS 层数是记录距离的手段。三件套齐全，问题就转化成了标准的图上 BFS。

类似的扩散模型在很多地方都能见到。比如矩阵上的多源 BFS 题，初始把多个源点放进队列，然后按层向外扩散，轮次本身就是距离。LeetCode 里不少题目都长在同一套骨架上：起点不一定是根，扩散方向不一定是单向，但“距离 + 逐层扩展”的思维完全一致。把 863 的图化思维吃透，再去做那些题会轻松很多。

6.3 另一个延伸方向：LCA 距离公式

如果你已经熟悉最近公共祖先（LCA）和节点的深度计算，其实还有一个暴力但不失为一种思考方式的方案：对树中每个节点 X，计算它到 target 的距离，如果等于 K 就加入答案。距离可以通过depth[X] + depth[target] - 2 * depth[LCA(X, target)]得到。这个思路的正确性毋庸置疑，但每求一对节点的 LCA 都要付出额外代价，整体复杂度会偏高，所以通常是作为理论验证，而不是最优解。

实践中我会把 863 当作“图化 + BFS”的典型例题，把 LCA 思路当作检查手段：写完了想验证答案对不对，可以手动算几对节点的 LCA 距离比对一下。

6.4 个人实战建议

这道题我强烈建议每种解法都亲手写一遍。第一遍写父指针 + BFS，重点是把“树要补反向边”这个思维定式建立起来；第二遍写递归回溯，重点体会递归调用栈怎么代替了显式的哈希表。两遍写完，你对“树上的距离”这类问题会有完全不同的感觉。

如果只打算在面试前记住一种写法，我会选递归回溯，因为它不需要额外哈希表，代码量更短。但前提是你真的把collect只向下收集的原则讲清楚，以及k - leftDist - 2这个减二的推导过程能当场说明白。否则面试官追问起来，容易卡壳。能在白板上一步步推出那个减二，比背代码更能体现自己真正理解了递归回溯的本质。