leetcode2389--感染二叉树需要的总时间

1. 题意

给定一个节点，每秒该节点会感染相邻的节点，受感染的节点下一秒也会感染周围节点；

求使得所有节点感染的时间

2. 题解

2.1 dfs建图+bfs搜索层次

我们将目标节点找到，并从该节点出发找到以该节点形成的树的深度即可。

• 我的代码

/**
 * 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:


    // * transform tree to graph

    // * sparse graph

    void build_graph(TreeNode * root, vector<vector<int>> &g) {
        if (nullptr == root)
            return;
        if ( root->left) {
            g[root->val].push_back( root->left->val);
            g[root->left->val].push_back(root->val);
            build_graph(root->left, g);
        }
        if ( root->right ) {
            g[root->val].push_back(root->right->val);
            g[root->right->val].push_back(root->val);
            build_graph(root->right, g);
        }
    }


    int amountOfTime(TreeNode* root, int start) {
        
        const int MAXN = 1e5 + 1;
        vector<vector<int>> g(MAXN, vector<int>());

        build_graph(root, g);

        int ans = 0;
        int last = start;
        queue<int> q;
        q.push(start);
        vector<int> vis(MAXN, 0);


        while (!q.empty()) {
            int cur = q.front();
            q.pop();vis[cur] = 1;

            for (int v:g[cur])
                if (!vis[v])
                    q.push(v);
            if (cur == last) {
                ans++;
                last = q.back();
            }

        }

        return ans - 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

2.2 dfs建图+dfs求深度

我们需要找到每个节点的父节点，并且用一个from来表示当前节点是从哪来的以避免重复遍历。

• 我的代码

/**
 * 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:


    // * transform tree to graph

    // * sparse graph

    void get_fa(unordered_map<int,TreeNode *> &fa, TreeNode *root, 
        int start, TreeNode *&start_node) {
        if (root == nullptr)
            return;
        if ( root->left)
            fa[root->left->val] = root;
        if ( root->right)
            fa[root->right->val] = root;
        if ( root->val == start)
            start_node = root;


        get_fa(fa, root->left, start, start_node );
        get_fa(fa, root->right, start, start_node );
    }

    int getDepth(TreeNode *root, int from,const unordered_map<int,TreeNode*> &fa) {
        
        if ( nullptr == root)
            return -1;

        int llen = -1;
        int rlen = -1;
        int flen = -1;

        if ( root->left && root->left->val != from)
            llen = getDepth(root->left, root->val, fa);
        if ( root->right && root->right->val != from )
            rlen = getDepth( root->right, root->val, fa);
        
        
        if (fa.find(root->val) != fa.end() &&
            fa.at(root->val)->val != from) {
           // cout << "fa-" << fa.at(root->val)->val << endl;
            flen = getDepth( fa.at(root->val), root->val, fa);
        }
        

        int ans = max(llen, rlen);
        ans = max(flen, ans);

        return ans + 1;
    }

    int amountOfTime(TreeNode* root, int start) {
        
        unordered_map<int,TreeNode *> fa;
        

        TreeNode *start_node;
        get_fa( fa, root, start, start_node);
     


        return  getDepth(start_node, -1, fa);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

• 03xf题解

TreeNode* fa[100001]; // 哈希表会超时，改用数组

class Solution {
    int start;
    TreeNode* start_node;

    void dfs(TreeNode* node, TreeNode* from) {
        if (node == nullptr) {
            return;
        }
        fa[node->val] = from; // 记录每个节点的父节点
        if (node->val == start) {
            start_node = node; // 找到 start
        }
        dfs(node->left, node);
        dfs(node->right, node);
    }

    int maxDepth(TreeNode* node, TreeNode* from) {
        if (node == nullptr) {
            return -1; // 注意这里是 -1，因为 start 的深度为 0
        }
        int res = -1;
        if (node->left != from) {
            res = max(res, maxDepth(node->left, node));
        }
        if (node->right != from) {
            res = max(res, maxDepth(node->right, node));
        }
        if (fa[node->val] != from) {
            res = max(res, maxDepth(fa[node->val], node));
        }
        return res + 1;
    }

public:
    int amountOfTime(TreeNode* root, int start) {
        this->start = start;
        dfs(root, nullptr);
        return maxDepth(start_node, start_node);
    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/2753470/cong-liang-ci-bian-li-dao-yi-ci-bian-li-tmt0x/comments/2287846/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

2.3 一次遍历

• 03xf

class Solution {
    int ans = 0, start;

    pair<int, bool> dfs(TreeNode* node) {
        if (node == nullptr) {
            return {0, false};
        }
        auto [l_len, l_found] = dfs(node->left);
        auto [r_len, r_found] = dfs(node->right);
        if (node->val == start) {
            // 计算子树 start 的最大深度
            // 注意这里和方法一的区别，max 后面没有 +1，所以算出的也是最大深度
            ans = max(l_len, r_len);
            return {1, true}; // 找到了 start
        }
        if (l_found || r_found) {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = max(ans, l_len + r_len); // 两条链拼成直径
            // 保证 start 是直径端点
            return {(l_found ? l_len : r_len) + 1, true};
        }
        return {max(l_len, r_len) + 1, false};
    }

public:
    int amountOfTime(TreeNode* root, int start) {
        this->start = start;
        dfs(root);
        return ans;
    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/solutions/2753470/cong-liang-ci-bian-li-dao-yi-ci-bian-li-tmt0x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36