Medium

题目描述

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 ，同时给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

  • 节点此前还没有感染。
  • 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数。

示例 1：

输入：root = [1,5,3,null,4,10,6,9,2], start = 3
输出：4
解释：节点按以下过程被感染：
- 第 0 分钟：节点 3
- 第 1 分钟：节点 1、10、6
- 第 2 分钟：节点 5
- 第 3 分钟：节点 4
- 第 4 分钟：节点 9、2
感染整棵树需要 4 分钟，所以返回 4 。

示例 2：

输入：root = [1], start = 1
输出：0
解释：第 0 分钟，树中唯一一个节点被感染，所以返回 0 。

提示：

  • 树中节点的数目在范围 [1, 10^5] 内
  • 1 <= Node.val <= 10^5
  • 每个节点的值 互不相同
  • 树中必定存在值为 start 的节点

解题思路

这道题可以转化为图的最短路径问题。关键思路是将二叉树转换为无向图，然后从起始感染节点进行广度优先搜索（BFS）。

解法一：构建邻接表 + BFS

首先通过深度优先搜索（DFS）遍历二叉树，构建邻接表表示的无向图。对于每个节点，它与其父节点、左子节点、右子节点都有边相连。

然后从起始感染节点开始进行BFS，每一轮BFS代表一分钟的感染扩散。使用队列记录当前感染的节点，使用访问标记避免重复感染。最终的BFS层数就是感染整棵树需要的时间。

解法二：一次DFS计算距离

更高效的做法是直接在DFS过程中计算每个节点到起始节点的距离。可以先找到起始节点的位置，然后计算从起始节点出发到达其他所有节点的最大距离。

推荐使用解法一，因为思路更清晰，代码更容易理解和实现。

代码实现

class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        unordered_map<int, vector<int>> graph;
        
        // 构建邻接表
        function<void(TreeNode*)> buildGraph = [&](TreeNode* node) {
            if (!node) return;
            
            if (node->left) {
                graph[node->val].push_back(node->left->val);
                graph[node->left->val].push_back(node->val);
                buildGraph(node->left);
            }
            
            if (node->right) {
                graph[node->val].push_back(node->right->val);
                graph[node->right->val].push_back(node->val);
                buildGraph(node->right);
            }
        };
        
        buildGraph(root);
        
        // BFS
        queue<int> q;
        unordered_set<int> visited;
        
        q.push(start);
        visited.insert(start);
        
        int time = -1;
        
        while (!q.empty()) {
            int size = q.size();
            time++;
            
            for (int i = 0; i < size; i++) {
                int node = q.front();
                q.pop();
                
                for (int neighbor : graph[node]) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        q.push(neighbor);
                    }
                }
            }
        }
        
        return time;
    }
};

class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        from collections import defaultdict, deque
        
        graph = defaultdict(list)
        
        # 构建邻接表
        def build_graph(node):
            if not node:
                return
            
            if node.left:
                graph[node.val].append(node.left.val)
                graph[node.left.val].append(node.val)
                build_graph(node.left)
            
            if node.right:
                graph[node.val].append(node.right.val)
                graph[node.right.val].append(node.val)
                build_graph(node.right)
        
        build_graph(root)
        
        # BFS
        queue = deque([start])
        visited = {start}
        time = -1
        
        while queue:
            size = len(queue)
            time += 1
            
            for _ in range(size):
                node = queue.popleft()
                
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        
        return time

public class Solution {
    public int AmountOfTime(TreeNode root, int start) {
        var graph = new Dictionary<int, List<int>>();
        
        // 构建邻接表
        void BuildGraph(TreeNode node) {
            if (node == null) return;
            
            if (!graph.ContainsKey(node.val)) {
                graph[node.val] = new List<int>();
            }
            
            if (node.left != null) {
                graph[node.val].Add(node.left.val);
                if (!graph.ContainsKey(node.left.val)) {
                    graph[node.left.val] = new List<int>();
                }
                graph[node.left.val].Add(node.val);
                BuildGraph(node.left);
            }
            
            if (node.right != null) {
                graph[node.val].Add(node.right.val);
                if (!graph.ContainsKey(node.right.val)) {
                    graph[node.right.val] = new List<int>();
                }
                graph[node.right.val].Add(node.val);
                BuildGraph(node.right);
            }
        }
        
        BuildGraph(root);
        
        // BFS
        var queue = new Queue<int>();
        var visited = new HashSet<int>();
        
        queue.Enqueue(start);
        visited.Add(start);
        
        int time = -1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            time++;
            
            for (int i = 0; i < size; i++) {
                int node = queue.Dequeue();
                
                if (graph.ContainsKey(node)) {
                    foreach (int neighbor in graph[node]) {
                        if (!visited.Contains(neighbor)) {
                            visited.Add(neighbor);
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }
        
        return time;
    }
}

var amountOfTime = function(root, start) {
    const graph = new Map();
    
    // 构建邻接表
    function buildGraph(node) {
        if (!node) return;
        
        if (!graph.has(node.val)) {
            graph.set(node.val, []);
        }
        
        if (node.left) {
            graph.get(node.val).push(node.left.val);
            if (!graph.has(node.left.val)) {
                graph.set(node.left.val, []);
            }
            graph.get(node.left.val).push(node.val);
            buildGraph(node.left);
        }
        
        if (node.right) {
            graph.get(node.val).push(node.right.val);
            if (!graph.has(node.right.val)) {
                graph.set(node.right.val, []);
            }
            graph.get(node.right.val).push(node.val);
            buildGraph(node.right);
        }
    }
    
    buildGraph(root);
    
    // BFS
    const queue = [start];
    const visited = new Set([start]);
    let time = -1;
    
    while (queue.length > 0) {
        const size = queue.length;
        time++;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            
            if (graph.has(node)) {
                for (const neighbor of graph.get(node)) {
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
        }
    }
    
    return time;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 是二叉树中节点的数量。时间复杂度包括构建邻接表的 O(n) 和 BFS 遍历的 O(n)。空间复杂度主要来自邻接表存储和 BFS 队列。

相关题目