Leetcode 2385 - Amount of Time for Binary Tree to Be Infected

題目

Problem#

給你一個 binary tree 的 root 上面的值都不重複，另外給你一個數字 start，問你從該數字的 node 為 root，最大深度為多少?

測資限制#

• $1 \le n \le 10^5$
• $1 \le val \le 10^5$

想法#

遍歷整個二元樹之後建成無向圖，接著再從起點開始遍歷找最大深度即可

AC Code#

Copy

class Solution
{
public:
    // node to id
    unordered_map<TreeNode*, int> g;
    int gid = 0;
    int getID(TreeNode* p)
    {
        if(!g.count(p))
        {
            g[p] = gid++;
            G.resize(gid);
        }
        return g[p];
    }
    // graph
    vector<vector<int>> G;
    void addEdge(int a, int b)
    {
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int st; // starting node
    void build(TreeNode* n, int x)
    {
        if(n->val == x)
        {
            st = getID(n);
        }
 
        if(n->left)
        {
            addEdge(getID(n), getID(n->left));
            build(n->left, x);
        }
        if(n->right)
        {
            addEdge(getID(n), getID(n->right));
            build(n->right, x);
        }
    }
 
    int bfs(int x)
    {
        int ans = INT_MIN;
        queue<pair<int,int>> q; // depth, idx
        unordered_set<int> vis;
        q.emplace(0, x);
        vis.insert(x);
        while(!q.empty())
        {
            auto [depth, i] = q.front();
            ans = max(ans, depth);
            q.pop();
            for(auto j : G[i])
            {
                if(!vis.count(j))
                {
                    q.emplace(depth+1, j);
                    vis.insert(j);
                }
            }
        }
        return ans;
    }
 
    int amountOfTime(TreeNode* r, int s)
    {
        gid = 0;
        g.clear();
        G.clear();
 
        build(r, s);
        return bfs(st);
    }
};

view raw leetcode/2385.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

心得#

原本想寫不建圖的，但後來放棄ㄌ