Medium

题目描述

给定一个二叉树（具有根结点 root），一个目标结点 target，和一个整数值 k，返回到目标结点 target 距离为 k 的所有结点的值的数组。

答案可以以任何顺序返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

示例 2：

输入：root = [1], target = 1, k = 3
输出：[]

提示：

  • 节点数在 [1, 500] 范围内
  • 0 <= Node.val <= 500
  • 所有节点 Node.val 唯一
  • 目标结点 target 是树上的结点
  • 0 <= k <= 1000

解题思路

这道题要求找到二叉树中距离目标节点 k 距离的所有节点。核心思路是将树转换为无向图，然后使用 BFS 进行搜索。

主要思路：

  1. 构建父节点映射：由于二叉树只有父节点到子节点的连接，我们需要先遍历树建立子节点到父节点的映射关系，这样就能在搜索时向上移动。

  2. BFS搜索：从目标节点开始，使用广度优先搜索向所有方向（左子节点、右子节点、父节点）扩展。每次扩展距离增加1，当距离达到k时，将当前层的所有节点加入结果。

  3. 避免重复访问：使用访问集合记录已访问的节点，防止在搜索过程中重复访问同一节点。

算法步骤：

  • 第一步：DFS遍历建立父节点映射
  • 第二步：从target开始BFS，使用队列存储当前层的节点
  • 第三步：每次处理一层节点，距离加1，直到距离为k

这种方法将树的搜索问题转化为图的搜索问题，思路清晰且易于实现。时间复杂度为O(n)，其中n是树中节点的数量。

代码实现

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        unordered_map<TreeNode*, TreeNode*> parent;
        
        // 建立父节点映射
        function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* node, TreeNode* par) {
            if (!node) return;
            parent[node] = par;
            dfs(node->left, node);
            dfs(node->right, node);
        };
        dfs(root, nullptr);
        
        // BFS搜索距离为k的节点
        queue<TreeNode*> q;
        unordered_set<TreeNode*> visited;
        
        q.push(target);
        visited.insert(target);
        
        int distance = 0;
        while (!q.empty() && distance < k) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 检查左子节点
                if (node->left && visited.find(node->left) == visited.end()) {
                    q.push(node->left);
                    visited.insert(node->left);
                }
                
                // 检查右子节点
                if (node->right && visited.find(node->right) == visited.end()) {
                    q.push(node->right);
                    visited.insert(node->right);
                }
                
                // 检查父节点
                if (parent[node] && visited.find(parent[node]) == visited.end()) {
                    q.push(parent[node]);
                    visited.insert(parent[node]);
                }
            }
            distance++;
        }
        
        vector<int> result;
        while (!q.empty()) {
            result.push_back(q.front()->val);
            q.pop();
        }
        
        return result;
    }
};

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # 建立父节点映射
        parent = {}
        
        def dfs(node, par):
            if node:
                parent[node] = par
                dfs(node.left, node)
                dfs(node.right, node)
        
        dfs(root, None)
        
        # BFS搜索距离为k的节点
        queue = collections.deque([target])
        visited = {target}
        
        distance = 0
        while queue and distance < k:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                
                # 检查左子节点
                if node.left and node.left not in visited:
                    queue.append(node.left)
                    visited.add(node.left)
                
                # 检查右子节点
                if node.right and node.right not in visited:
                    queue.append(node.right)
                    visited.add(node.right)
                
                # 检查父节点
                if parent[node] and parent[node] not in visited:
                    queue.append(parent[node])
                    visited.add(parent[node])
            
            distance += 1
        
        return [node.val for node in queue]

public class Solution {
    public IList<int> DistanceK(TreeNode root, TreeNode target, int k) {
        Dictionary<TreeNode, TreeNode> parent = new Dictionary<TreeNode, TreeNode>();
        
        // 建立父节点映射
        void Dfs(TreeNode node, TreeNode par) {
            if (node == null) return;
            parent[node] = par;
            Dfs(node.left, node);
            Dfs(node.right, node);
        }
        
        Dfs(root, null);
        
        // BFS搜索距离为k的节点
        Queue<TreeNode> queue = new Queue<TreeNode>();
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        
        queue.Enqueue(target);
        visited.Add(target);
        
        int distance = 0;
        while (queue.Count > 0 && distance < k) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                
                // 检查左子节点
                if (node.left != null && !visited.Contains(node.left)) {
                    queue.Enqueue(node.left);
                    visited.Add(node.left);
                }
                
                // 检查右子节点
                if (node.right != null && !visited.Contains(node.right)) {
                    queue.Enqueue(node.right);
                    visited.Add(node.right);
                }
                
                // 检查父节点
                if (parent[node] != null && !visited.Contains(parent[node])) {
                    queue.Enqueue(parent[node]);
                    visited.Add(parent[node]);
                }
            }
            distance++;
        }
        
        IList<int> result = new List<int>();
        while (queue.Count > 0) {
            result.Add(queue.Dequeue().val);
        }
        
        return result;
    }
}

var distanceK = function(root, target, k) {
    const parent = new Map();
    
    // 建立父节点映射
    function dfs(node, par) {
        if (!node) return;
        parent.set(node, par);
        dfs(node.left, node);
        dfs(node.right, node);
    }
    
    dfs(root, null);
    
    // BFS搜索距离为k的节点
    const queue = [target];
    const visited = new Set([target]);
    
    let distance = 0;
    while (queue.length > 0 && distance < k) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            
            // 检查左子节点
            if (node.left && !visited.has(node.left)) {
                queue.push(node.left);
                visited.add(node.left);
            }
            
            // 检查右子节点
            if (node.right && !visited.has(node.right)) {
                queue.push(node.right);
                visited.add(node.right);
            }
            
            // 检查父节点
            if (parent.get(node) && !visited.has(parent.get(node))) {
                queue.push(parent.get(node));
                visited.add(parent.get(node));
            }
        }
        distance++;
    }
    
    return queue.map(node => node.val);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有节点建立父节点映射，BFS最多访问每个节点一次
空间复杂度O(n)父节点映射需要O(n)空间，BFS队列和访问集合最多存储O(n)个节点

相关题目