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

题目描述
给定一个二叉树的根节点 root，一个目标节点 target，和一个整数 k。需要返回所有与 target 距离为 k 的节点值。这里的距离指的是从 target 到当前节点需要经过的边数。

示例
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：节点 5 的距离为 2 的节点是 7、4 和 1。

解题过程

步骤 1：问题分析
在二叉树中，节点间路径是唯一的。但目标节点可能位于树的任意位置，距离为 k 的节点可能位于：

1. 目标节点的子树中（向下搜索）
2. 目标节点的祖先节点及其他分支（向上搜索）

直接使用二叉树结构只能向下遍历，因此需要记录父节点信息以实现向上搜索。

步骤 2：构建父节点映射
通过深度优先搜索（DFS）遍历树，为每个节点记录其父节点：

def build_parent_map(node, parent, parent_map):
    if node is None:
        return
    parent_map[node] = parent
    build_parent_map(node.left, node, parent_map)
    build_parent_map(node.right, node, parent_map)

• 使用字典 parent_map 存储每个节点对应的父节点。
• 根节点的父节点为 None。

步骤 3：广度优先搜索（BFS）查找距离为 k 的节点
从 target 节点出发进行 BFS，记录访问过的节点避免重复访问。当步数等于 k 时，记录当前层的所有节点：

from collections import deque

def find_nodes(root, target, k):
    parent_map = {}
    build_parent_map(root, None, parent_map)  # 构建父节点映射
    
    queue = deque([target])
    visited = set([target])
    distance = 0
    
    while queue:
        if distance == k:
            return [node.val for node in queue]  # 返回当前层所有节点值
        
        # 遍历当前层的所有节点
        for _ in range(len(queue)):
            node = queue.popleft()
            # 检查左子节点
            if node.left and node.left not in visited:
                visited.add(node.left)
                queue.append(node.left)
            # 检查右子节点
            if node.right and node.right not in visited:
                visited.add(node.right)
                queue.append(node.right)
            # 检查父节点
            parent = parent_map.get(node)
            if parent and parent not in visited:
                visited.add(parent)
                queue.append(parent)
        
        distance += 1
    
    return []  # 如果没有距离为k的节点

步骤 4：详细执行流程

1. 构建父节点映射：遍历整棵树，记录每个节点的父节点。
2. BFS 初始化：从 target 开始，初始化队列和已访问集合。
3. 层级遍历：
   • 每次处理一层的所有节点。
   • 对每个节点，检查其左子节点、右子节点和父节点，若未访问则加入队列。
   • 当步数 distance 等于 k 时，当前队列中的所有节点即为结果。

关键点

• 通过父节点映射将树转换为无向图，使 BFS 可向任意方向搜索。
• 使用 visited 集合避免重复访问节点（如子节点访问父节点后又回到子节点）。
• BFS 按层遍历的特性保证首次到达距离 k 时即为最短路径。

复杂度分析

• 时间复杂度：O(n)，每个节点最多被访问一次。
• 空间复杂度：O(n)，存储父节点映射和 BFS 队列。