Amount of Time for Binary Tree to Be Infected

leetcode 2385. Amount of Time for Binary Tree to Be Infected

Intuition: DFS

Usually, Problems related with Tree is solvable with DFS. This is one of the examples.

It provide a starting value, so want to find it first with dfs(). I use status in this function. Once it meets start node, it will return 1, return -1 contrarily.

res is the maximum time we want to return, and count means how far we have backtracked from the start node.

findMax() use dfs to find the maximum time spend infected all leef of root;

Code

cpp

int findMax(TreeNode* root) {
    return (!root) ? -1 : max(findMax(root->left)+1, findMax(root->right)+1);
}
int res = 0, count = 0;
int dfs(TreeNode* root, int start) {
    if(!root) return -1;
    if(root->val == start){
        res = max(res, findMax(root));
        return 1;
    }
    int a = dfs(root->left, start);
    int b = dfs(root->right, start);
    if(a != -1 || b != -1)
        count++;
    else
        return -1;
    if(a != -1) res = max(res, findMax(root->right) + 1 + count);
    if(b != -1) res = max(res, findMax(root->left) + 1 + count);
    return 1;
}
int amountOfTime(TreeNode* root, int start) {
    int a = dfs(root, start);
    return res;
}

Complexity Analysis

Time: O(n^2)

Space: O(1)

Amount of Time for Binary Tree to Be Infected ​

Intuition: DFS ​

Code ​

Complexity Analysis ​

Amount of Time for Binary Tree to Be Infected

Intuition: DFS

Code

Complexity Analysis