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

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

题目描述

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

image-20220922002853294

image-20220922002857929

题意分析

给定一棵二叉树、树中的一个目标节点 target 和一个整数 k，要求返回所有到 target 的距离恰好为 k 的节点值。这里的距离指两点之间最短路径上的边数，答案的顺序不作要求。

读题最关键的一处是：距离是在「树作为图」的意义下定义的，而不是「target 的子树深度」。从 target 出发的路径既可以往下走到孩子，也可以先往上走到父亲、再从父亲拐到另一棵子树里去。所以答案里通常同时包含 target 的后代、祖先，以及祖先的另一侧分支上的节点。

而给定的数据结构只有 left 和 right 两根向下的指针，没有指向父亲的引用。这就是本题的信息缺口：题目要的是无向意义下的距离，手里拿到的却是只能单向下行的结构。补上这个缺口，题目就没有难点了。

约束里还有几条信号。节点总数不超过 500，值互不相同且都在 [0, 500] 内，说明可以放心地对每个节点建立映射，$O(n)$ 的额外空间完全没有压力；k 的上界是 1000，明显大于树的可能高度，说明「k 大到走不到任何节点」是必须处理的正常情况，此时返回空列表。

边界情形：k = 0 时答案就是 target 自己（距离为 0 的节点只有它自身）；target 是根节点时只能向下走；target 是叶子时第一步只能向上走；k 超过树的规模时答案为空；树只有一个节点时除了 k = 0 都返回空。

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

核心思路

从 target 到其他节点的路径既可能向下走孩子，也可能向上走父节点，但原二叉树没有父指针。先 DFS 建立 parent 映射，相当于给每条父子边补上反向边，把树转换为无向图；之后从 target 做分层 BFS，层数就是最短距离。

BFS 的不变量是：队列当前保存的节点到 target 的距离都等于 distance，并且每个节点只会入队一次。每轮只扩展这一层的固定数量节点，将左孩子、右孩子和父节点三个邻居加入下一层。补了反向边后父子之间可以来回走，因此必须用 visited 去重，并在入队时立即标记。

扩展恰好 k 层后，队列中剩余的就是距离为 k 的全部节点。这个收尾自然覆盖两个边界：k = 0 时队列仍只有 target；若 k 过大，队列会提前耗尽，结果为空。

解题步骤

  1. DFS 遍历整棵树，记录 parent[node] = parentNode，根节点的父节点为 null。
  2. 将 target 入队并立即加入 visited，令 distance = 0。
  3. 当队列非空且 distance < k 时，先固定本层大小，再逐个扩展节点的左孩子、右孩子和父节点。
  4. 邻居非空且未访问时才入队，并立刻标记；一层处理完后执行 distance++。
  5. 循环结束后，收集队列中所有节点值作为答案。

示例中 target = 5、k = 2：第 0 层为 [5]，第 1 层为 [6, 2, 3]，第 2 层为 [7, 4, 1]，因此返回 [7, 4, 1]。节点 1 正是通过 5 → 3 → 1 这条先向上再向下的路径找到的。

代码实现

import java.util.*;

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)$。父指针表、访问集合、队列及最坏情况下的递归栈均为线性规模。

关键点总结

  • 题目给的是单向二叉树，距离却按无向路径定义；父指针表补齐了缺失的反向边。
  • BFS 层号天然对应最短距离，比为每个节点单独计算路径更直接。
  • 一旦把树视为无向图，visited 就不可省，否则父子节点会反复入队。
  • 父指针表应以节点引用为键，不能依赖节点值唯一这一偶然条件。
  • 面试表述顺序：指出方向缺口，补父边转成图，再用 BFS 取第 k 层。

易错点总结

  • 只向左右孩子搜索会漏掉经过祖先到达的节点，如示例中的节点 1。
  • target 必须在入队时就标记；否则下一层会沿父子边把它重复加入。
  • 每层开始前要固定队列长度，否则本层与下一层会混在同一轮处理。
  • 循环条件应为 distance < k；写成 <= 会多扩展一层，也会破坏 k = 0。
  • 收集的是扩展 k 层后的队列，而不是遍历过程中遇到的所有节点。

相似题目

题目 难度 考察点
1650. 二叉树的最近公共祖先 III 中等 节点自带 parent 指针，省去建表这一步，直接沿父链上行做相交
236. 二叉树的最近公共祖先 中等 只有下行指针时如何自底向上回传信息，是本题「不建父表」解法的前置技能
1245. 树的直径 中等 输入直接给的是无向边表，两次 BFS 求最远点，省掉了补反向边的环节
994. 腐烂的橘子 中等 同样用 BFS 层号当时间，但起点有多个，是多源版本的分层扩展
542. 01 矩阵 中等 多源 BFS 求每个格子的最短距离，邻居由坐标偏移枚举而非指针给出
133. 克隆图 中等 无向图上用哈希表建立「原节点到新节点」的映射，与本题建父表的记账方式同构
1466. 重新规划路线 中等 显式地给有向边补上反向边再遍历，把「补反向边」这一手法单独拎出来考
102. 二叉树的层序遍历 中等 纯下行的分层 BFS，本题去掉父指针后就退化成它，可用来校验分层写法是否正确
1091. 二进制矩阵中的最短路径 中等 网格图上求最短路径长度，邻居有八个方向，考察 BFS 层号与距离的等价关系