跳到主要内容

LeetCode 863. 二叉树中所有距离为 K 的结点

本节目标

建立父节点映射，把树转为可双向移动的状态图后从目标节点按层 BFS。

这是树上综合问题中把单向父子关系转换为无向图搜索的题目。

查看 LeetCode 原题

题意与边界​

给定树中的目标节点 target 和非负整数 k，返回与它距离恰为 k 条边的所有节点。结果顺序任意；k = 0 时答案只有目标本身，超过树高时返回空。原题保证节点值唯一；实现仍按节点身份维护父节点表和访问状态，使图搜索语义不依赖数值。

父节点映射与 BFS​

从根 DFS 一次，建立每个节点到父节点的映射。此后任一节点的邻居是 left、right、parent 三者，树就成为一张无向图。再从 target 开始 BFS：入队时立即把节点对象加入 visited，防止沿“孩子—父亲—孩子”往返成环。

每轮处理固定的队列长度，恰好走过一条边；当轮数达到 k，当前队列就是所有答案节点。测试排序后比较结果，因为不同邻居入队顺序不影响集合。

正确性依据​

父节点映射补齐了树中每条边的反向方向，因此 BFS 的邻接关系与原树的无向边完全一致。BFS 第 d 层恰包含从目标经过 d 条边可达的节点；visited 使每个节点只在最短距离层入队一次，也阻止双向边形成循环。故第 k 层恰为所有且仅有距离为 k 的节点。

代码实现​

C++17
class Solution {
public:
    std::vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        std::unordered_map<TreeNode*, TreeNode*> parent;
        buildParent(root, nullptr, parent);

        std::queue<TreeNode*> queue;
        std::unordered_set<TreeNode*> visited;
        queue.push(target);
        visited.insert(target);
        int distance = 0;
        while (!queue.empty()) {
            if (distance == k) {
                std::vector<int> answer;
                while (!queue.empty()) {
                    answer.push_back(queue.front()->val);
                    queue.pop();
                }
                return answer;
            }

            int size = static_cast<int>(queue.size());
            for (int i = 0; i < size; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                for (TreeNode* neighbor : {node->left, node->right, parent[node]}) {
                    if (neighbor != nullptr && visited.insert(neighbor).second) {
                        queue.push(neighbor);
                    }
                }
            }
            distance++;
        }
        return {};
    }

private:
    void buildParent(
        TreeNode* node,
        TreeNode* previous,
        std::unordered_map<TreeNode*, TreeNode*>& parent
    ) {
        if (node == nullptr) {
            return;
        }

        parent[node] = previous;
        buildParent(node->left, node, parent);
        buildParent(node->right, node, parent);
    }
};

复杂度分析​

建映射和 BFS 都至多访问每个节点一次，时间复杂度为 O(n)。父节点表、访问集合和队列最坏占用 O(n) 额外空间。

边界与易错点​

  • 只向左右孩子搜索，遗漏必须先经过父节点的答案。
  • 未建立访问集合，双向边会让 BFS 来回循环。
  • 出队后才标记访问，重复邻居可能被多次入队。
  • 即使原题保证值唯一，也用节点对象作映射键，避免把图搜索语义错误地绑定到数值。
  • 到第 k 层后继续扩展，返回了距离更远的节点。

模式迁移​

当原结构只给出单向指针、问题却要求反向移动或最短距离时，可以先显式补出反向边，再使用普通图 BFS。带权边或多源起点则分别迁移到最短路和多源 BFS 模型。