感染二叉树需要的总时间 图解题解

这道题到底在问什么

输入

root=[1,5,3,null,4,10,6,9,2], start=3

输出

4

输入

root=[1], start=1

输出

0

最优解：一步一步想明白

1. 3记牢两步:先把父子边记成双向,再从 start 一层一层往外烧。最远那个节点是第几分钟烧到的,答案就是几。下面先建图,再点火。
2. 4先把树看成无向图开火之前先想清楚一件事。普通的树,我们习惯只从父往子走;可感染是不管方向的,火能从孩子烧回父亲。所以要先把这棵树改造成一张无向图:每一条父子连线,都当成一条来回都能走的路。紫色标出的就是起点 3。下面一条边一条边地把这张图建起来。
3. 5第 1 条边把节点 1 和它的孩子 5 之间这条边记下来,而且是双向的:从 1 能走到 5,反过来从 5 也能走回 1。这样一来,原本只能父到子的关系,现在孩子也能烧回父亲了。
4. 6第 2 条边把节点 5 和它的孩子 4 之间这条边记下来,而且是双向的:从 5 能走到 4,反过来从 4 也能走回 5。两个红色节点就是这条边的两头。
5. 7第 3 条边把节点 4 和它的孩子 9 之间这条边记下来,而且是双向的:从 4 能走到 9,反过来从 9 也能走回 4。两个红色节点就是这条边的两头。
6. 8第 4 条边把节点 4 和它的孩子 2 之间这条边记下来,而且是双向的:从 4 能走到 2,反过来从 2 也能走回 4。两个红色节点就是这条边的两头。
7. 9第 5 条边把节点 1 和它的孩子 3 之间这条边记下来,而且是双向的:从 1 能走到 3,反过来从 3 也能走回 1。两个红色节点就是这条边的两头。
8. 10第 6 条边把节点 3 和它的孩子 10 之间这条边记下来,而且是双向的:从 3 能走到 10,反过来从 10 也能走回 3。两个红色节点就是这条边的两头。
9. 11第 7 条边把节点 3 和它的孩子 6 之间这条边记下来,而且是双向的:从 3 能走到 6,反过来从 6 也能走回 3。这是最后一条边,七条父子边全部记成了双向,无向图建好了。
10. 12已感染: 3图建好了,回到起点。第 0 分钟,只有值为 3 的节点着火,把它标成焦点色。它到自己的距离是 0。接下来每过一分钟,火就从已经着火的节点向所有还没烧到的邻居蔓延一圈。
11. 13邻居: 1、10、6在无向图里看看 3 的邻居有哪些:父亲 1,孩子 10,孩子 6,一共三个,都用红色圈出。注意父亲 1 也在里面,这正是普通往下搜索会漏掉的一支。这三个节点现在都紧挨着火源,下一分钟它们会一起被点燃。
12. 14新感染: 1、10、6第 1 分钟到,这几个红色候选一起被点燃: 1、10、6。它们和火源的距离都是 1,所以恰好在第 1 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
13. 15候选: 5轮到从节点 1 往外看。它的孩子 5 还没着火,标红当候选;孩子 3 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
14. 16这支到头再看节点 10。它连着的只有 3,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
15. 17这支到头再看节点 6。它连着的只有 3,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
16. 18新感染: 5第 2 分钟到,被点燃的是: 5。它们和火源的距离都是 2,所以恰好在第 2 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
17. 19候选: 4轮到从节点 5 往外看。它的孩子 4 还没着火,标红当候选;父亲 1 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
18. 20新感染: 4第 3 分钟到,被点燃的是: 4。它们和火源的距离都是 3,所以恰好在第 3 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
19. 21候选: 9、2轮到从节点 4 往外看。它的孩子 9、2 还没着火,标红当候选;父亲 5 已经烧过了,跳过不重复。所以下一分钟的火会从这里继续蔓延。
20. 22新感染: 9、2第 4 分钟到,这几个红色候选一起被点燃: 9、2。它们和火源的距离都是 4,所以恰好在第 4 分钟烧到。已经烧过的节点标成蓝色,刚点燃的用焦点色。
21. 23这支到头再看节点 9。它连着的只有 4,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
22. 24这支到头再看节点 2。它连着的只有 4,早就烧过了,这一支到头,没有新节点可点。它是这条路的尽头。
23. 25扩散停止再往下试一分钟,看看最后点燃的 9、2 还能不能烧到新节点。它们都是叶子,连着的父亲早已着火,没有任何新目标。火到此彻底熄灭,不会再有第 5 分钟的战果。
24. 26感染全树用了 4 分钟把整场火回放一遍。第 0 分钟是 3,第 1 分钟 1、10、6,第 2 分钟 5,第 3 分钟 4,第 4 分钟 9 和 2。最远的 9 和 2 是第 4 分钟才烧到的,那就是全树感染完成的时刻。所以答案就是 start 到最远节点的距离,等于 4。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        def dfs(node: Optional[TreeNode], fa: Optional[TreeNode]):
            if node is None:
                return
            if fa:
                g[node.val].append(fa.val)
                g[fa.val].append(node.val)
            dfs(node.left, node)
            dfs(node.right, node)

        def dfs2(node: int, fa: int) -> int:
            ans = 0
            for nxt in g[node]:
                if nxt != fa:
                    ans = max(ans, 1 + dfs2(nxt, node))
            return ans

        g = defaultdict(list)
        dfs(root, None)
        return dfs2(start, -1)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        unordered_map<int, vector<int>> g;
        function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* node, TreeNode* fa) {
            if (!node) {
                return;
            }
            if (fa) {
                g[node->val].push_back(fa->val);
                g[fa->val].push_back(node->val);
            }
            dfs(node->left, node);
            dfs(node->right, node);
        };
        function<int(int, int)> dfs2 = [&](int node, int fa) -> int {
            int ans = 0;
            for (int nxt : g[node]) {
                if (nxt != fa) {
                    ans = max(ans, 1 + dfs2(nxt, node));
                }
            }
            return ans;
        };
        dfs(root, nullptr);
        return dfs2(start, -1);
    }
};

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Map<Integer, List<Integer>> g = new HashMap<>();

    public int amountOfTime(TreeNode root, int start) {
        dfs(root, null);
        return dfs2(start, -1);
    }

    private void dfs(TreeNode node, TreeNode fa) {
        if (node == null) {
            return;
        }
        if (fa != null) {
            g.computeIfAbsent(node.val, k -> new ArrayList<>()).add(fa.val);
            g.computeIfAbsent(fa.val, k -> new ArrayList<>()).add(node.val);
        }
        dfs(node.left, node);
        dfs(node.right, node);
    }

    private int dfs2(int node, int fa) {
        int ans = 0;
        for (int nxt : g.getOrDefault(node, Collections.emptyList())) {
            if (nxt != fa) {
                ans = Math.max(ans, 1 + dfs2(nxt, node));
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问