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

约 6 分钟
文章信息 11 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 腾讯 字节 阿里 微软 美团 B站
标签
哈希表 深度优先搜索 树 广度优先搜索 二叉树

题目描述

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

image-20260928213951985

image-20260928213951986

image-20260928213951987

题意分析

给定二叉树、树中的目标节点 target 和距离 k，返回所有与目标节点恰好相隔 k 条边的节点值。距离统计的是边数，不是经过的节点数，答案顺序不限。

路径可以沿孩子向下，也可以沿父节点向上，再进入另一棵子树，所以不能只搜索目标节点的后代。k = 0 时答案是目标自身；如果树中没有这么远的节点，返回空列表。

解法：父节点映射 + BFS 分层

核心思路

[!blue]

二叉树节点只直接保存左右孩子，但计算距离时父子边可以双向经过。先从根遍历一遍，记录 parent[node]，就能在不改变原树的情况下，让每个节点都能找到左孩子、右孩子和父节点这三个可能邻居。

从 target 开始做 BFS。所有边长度都为 1，因此第 0 层只有目标，第 1 层是与它相邻的节点，每处理完一整层，新加入的节点就恰好比这一层远一条边。只扩展 k 层，便能得到全部距离为 k 的节点。

为了区分两层，开始处理一层前先保存队列当前大小 size，本轮只弹出这 size 个节点。处理中追加的邻居属于下一层，不能立即继续算在本轮里。完整处理一层后，队列才再次全部对应同一个距离。

加入父边后，可以从父亲走到孩子再返回父亲，因此需要 visited。目标入队时就标记，后续邻居也在首次入队时标记；已访问节点不再进入队列，既避免往返循环，也保证每个节点只在首次确定的最短距离层出现。

当距离达到 k 时，队列中留下的正是答案层，直接收集它们的值即可；若提前变空，说明所有能到达的节点都处理过，距离 k 的节点不存在。

解题步骤

  1. 从根 DFS，建立每个节点到父节点的映射；根的父节点记为空。
  2. 将 target 放入队列并标记为已访问，当前距离设为 0。
  3. 队列非空且距离小于 k 时，先固定本层大小，再逐个弹出本层节点。
  4. 对每个节点检查左孩子、右孩子和父节点；邻居非空且尚未访问时，立即标记并入队。
  5. 一层处理完后距离加一。停止扩展时收集队列中全部节点值并返回。

代码实现

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();

        buildParent(root, null, parent);

        Queue<TreeNode> queue = new ArrayDeque<>();
        Set<TreeNode> visited = new HashSet<>();

        queue.offer(target);
        visited.add(target);
        int distance = 0;

        while (!queue.isEmpty() && distance < k) {
            // 固定当前距离的一层节点，扩展完一整层才增加距离。
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                addNeighbor(node.left, queue, visited);
                addNeighbor(node.right, queue, visited);
                addNeighbor(parent.get(node), queue, visited);
            }

            distance++;
        }

        List<Integer> res = new ArrayList<>();

        while (!queue.isEmpty()) {
            res.add(queue.poll().val);
        }

        return res;
    }

    private void buildParent(TreeNode node, TreeNode pre, Map<TreeNode, TreeNode> parent) {
        if (node == null) {
            return;
        }

        parent.put(node, pre);
        buildParent(node.left, node, parent);
        buildParent(node.right, node, parent);
    }

    private void addNeighbor(TreeNode node, Queue<TreeNode> queue, Set<TreeNode> visited) {
        if (node != null && visited.add(node)) {
            // 访问集合避免从父子边来回走造成重复。
            queue.offer(node);
        }
    }
}

func distanceK(root *TreeNode, target *TreeNode, k int) []int {
    parent := make(map[*TreeNode]*TreeNode)
    var buildParent func(*TreeNode, *TreeNode)
    buildParent = func(node *TreeNode, pre *TreeNode) {
        if node == nil {
            return
        }
        parent[node] = pre
        buildParent(node.Left, node)
        buildParent(node.Right, node)
    }
    buildParent(root, nil)

    queue := []*TreeNode{
        target,
    }
    visited := map[*TreeNode]bool{target: true}
    distance := 0
    for len(queue) > 0 && distance < k {
        // 固定当前距离的一层节点，扩展完一整层才增加距离。
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            neighbors := []*TreeNode{
                node.Left,
                node.Right,
                parent[node],
            }
            for _, next := range neighbors {
                if next != nil && !visited[next] {
                    // 把父节点也作为相邻节点后，整棵树变成无向图。
                    visited[next] = true
                    queue = append(queue, next)
                }
            }
        }
        distance++
    }

    res := make([]int, 0, len(queue))
    for _, node := range queue {
        res = append(res, node.Val)
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。建父指针表访问每个节点一次，BFS 也至多访问每个节点一次。
  • 空间复杂度：$O(n)$。父指针表、访问集合、队列及最坏情况下的递归栈均为线性规模。

关键点总结

[!green]

  • 父节点表补齐向上移动的能力，把树当作无向连通结构搜索。
  • BFS 的层数就是边距离，层边界处的队列才完全属于同一距离。
  • 入队即标记，保证每个节点只在首次到达时参与扩展。

易错点总结

[!yellow]

  • 只搜索左右孩子，会漏掉目标的祖先以及经过祖先到达的其他分支。
  • 没有提前标记目标，下一层可能沿父子边把目标再次入队。
  • 一层内不断读取变化后的队列长度，会把新加入的下一层一起处理，距离计数失真。
  • 用 distance <= k 继续扩展，会多走一层，尤其会错误处理 k = 0。
  • 把搜索期间经过的全部节点加入结果，得到的是若干距离层的混合；这里只收集停止时的队列。
  • 父节点映射记录的是节点身份，不应把目标值当成节点引用使用。

相似题目

题目 难度 关联与区别
2385. 感染二叉树需要的总时间 中等 同样把树补上父边后从指定节点扩散，原题求到达全部节点的最大距离，本题只收集第k层。
742. 二叉树最近的叶节点 中等 同样允许从目标向父亲或孩子移动，原题首次遇叶子就停止，本题按指定距离截断。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/16177632
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！