Loading...
Loading...
You are given the root of a binary tree whose node values are all distinct, and an integer start that is the value of one of its nodes.
At minute 0, a signal appears on the node with value start. During each following minute, the signal spreads from every node that has it to all of that node's neighbors. A node's neighbors are its parent and its children.
Return the number of minutes until every node in the tree has the signal.
Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Node.val ≤105Node.val are distinct.start exists in the tree.Minute 0: node 3. Minute 1: its parent 1 and its children 10 and 6. Minute 2: node 5, a child of 1. Minute 3: node 4. Minute 4: nodes 9 and 2, the children of 4. Every node has the signal after 4 minutes.
The only node has the signal at minute 0, so no time is needed.
The signal climbs from 4 to 2 (minute 1) and to the root 1 (minute 2), then goes down to 3 (minute 3) and to 5 (minute 4).