2385. Amount of Time for Binary Tree to Be Infected

Problem

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

• The node is currently uninfected.

• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

  Example 1:

Input: root = [1,5,3,null,4,10,6,9,2], start = 3
Output: 4
Explanation: The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.

Example 2:

Input: root = [1], start = 1
Output: 0
Explanation: At minute 0, the only node in the tree is infected so we return 0.

  Constraints:

• The number of nodes in the tree is in the range [1, 10^5].

• 1 <= Node.val <= 10^5

• Each node has a unique value.

• A node with a value of start exists in the tree.

Solution (Java)

/**
 * 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 Solution {
    private int max = 0;

    public int amountOfTime(TreeNode root, int start) {
        dfs(root, start, new Distance(-1));
        return max;
    }

    private int dfs(TreeNode root, int start, Distance l) {
        if (root == null) {
            return 0;
        }
        Distance ld = new Distance(-1);
        Distance rd = new Distance(-1);
        int left = dfs(root.left, start, ld);
        int right = dfs(root.right, start, rd);
        if (l.val == -1 && start == root.val) {
            max = Math.max(left, right);
            l.val = 1;
        }
        if (ld.val != -1) {
            max = Math.max(max, ld.val + right);
            l.val = ld.val + 1;
        } else if (rd.val != -1) {
            max = Math.max(max, rd.val + left);
            l.val = rd.val + 1;
        }
        return Math.max(left, right) + 1;
    }

    private static class Distance {
        int val;

        Distance(int v) {
            this.val = v;
        }
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).