Minimum Time To Burn Tree
You are given an undirected tree with n nodes numbered from 0 to n - 1. The fire can start from any node, and you may choose the starting node to minimize the total burning time. In each time unit, fire spreads from every burning node to all of its adjacent nodes. Return the minimum time required to burn the entire tree.
Class
TreeBurning()
Methods
Minimum Burn Time
int minimumBurnTime(int n, List<String> edges)
- Returns the minimum number of time units needed to burn all nodes of the tree.
- The fire can start from any node.
- Each string in
edges is in the exact format "u,v" with no spaces.
- If multiple starting nodes give the same minimum time, only the time is returned.
Input Format
n: number of nodes in the tree.edges: list of strings where each string contains two comma-separated node indices.
Output Format
- Return an integer representing the minimum time required to burn the entire tree.
Constraints
1 ≤ n ≤ 100,000edges.size() = n - 10 ≤ u < n0 ≤ v < nu != v- The given edges always form a valid undirected tree.
Examples
Example 1
minimumBurnTime(n = 5, edges = ["0,1", "1,2", "1,3", "3,4"])
Output: 2
Explanation: Start the fire at node 1 or node 3. The farthest node burns after 2 time units.
Example 2
minimumBurnTime(n = 6, edges = ["0,1", "1,2", "2,3", "3,4", "4,5"])
Output: 3
Explanation: The tree is a straight chain. Starting from node 2 or node 3 burns all nodes in 3 time units.
Example 3
minimumBurnTime(n = 1, edges = [])
Output: 0
Explanation: The only node is already the starting node, so no time is needed to spread the fire.