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

0226

Problems

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.

Sample Test Case

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, 105].
1 <= Node.val <= 105
Each node has a unique value.
A node with a value of start exists in the tree.

Intuition

In a single unit of time, the tree will infect or burn 3 nodes.

  1. Parent Node.
  2. Left Child Node.
  3. Right Child Node.

The left and right child can be directly found using the pointers. We need to have extra logics to find the parent node. Once we have the parent node mapping, then a simple BFS starting from the triggering point is sufficient to find the amount of time.

Why BFS ? Because we have to go by breadth, we can burn all the children in a single unit of time level by level.

Approach

  • Use BFS to map the parent and also to find the target node.
  • Use another BFS to calculate the time.
  • Use a visited hashset to avoid re-infecting already infected node and recalculating the node again which will make the time calculation wrong.
  • Process all the parent, left child, right child if and only if its not visited.

Complexity

  • Time complexity:

    O(NumberOfNode) for target node finding and parent mapping + O(number of nodes) for calculating amount of time.

  • Space complexity:

    O(number of nodes) for parent map + O(number of nodes) for queues + O(Number of nodes) for visited set,

Code 

<span>/** * 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; * } * } */</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>int</span> <span>amountOfTime</span><span>(</span><span>TreeNode</span> <span>root</span><span>,</span> <span>int</span> <span>start</span><span>)</span> <span>{</span>
        <span>if</span> <span>(</span><span>root</span> <span>==</span> <span>null</span><span>)</span> <span>{</span>
            <span>return</span> <span>0</span><span>;</span>
        <span>}</span>
        <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span> <span>=</span> <span>new</span> <span>HashMap</span><span><>();</span>
        <span>TreeNode</span> <span>targetNode</span> <span>=</span> <span>findParentAndTargetNode</span><span>(</span><span>root</span><span>,</span> <span>parentMap</span><span>,</span> <span>start</span><span>);</span>
        <span>// this is added just to make sure we have a targetNode</span>
        <span>if</span> <span>(</span><span>targetNode</span> <span>==</span> <span>null</span><span>)</span> <span>{</span>
            <span>return</span> <span>0</span><span>;</span>
        <span>}</span>
        <span>return</span> <span>minimumTimeToInfect</span><span>(</span><span>targetNode</span><span>,</span> <span>parentMap</span><span>);</span>
    <span>}</span>
    <span>private</span> <span>int</span> <span>minimumTimeToInfect</span><span>(</span><span>TreeNode</span> <span>targetNode</span><span>,</span> <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span><span>)</span> <span>{</span>
        <span>Queue</span><span><</span><span>TreeNode</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>targetNode</span><span>);</span>
        <span>Set</span><span><</span><span>Integer</span><span>></span> <span>visited</span> <span>=</span> <span>new</span> <span>HashSet</span><span><>();</span>
        <span>visited</span><span>.</span><span>add</span><span>(</span><span>targetNode</span><span>.</span><span>val</span><span>);</span>
        <span>int</span> <span>infectTime</span> <span>=</span> <span>0</span><span>;</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>size</span> <span>=</span> <span>queue</span><span>.</span><span>size</span><span>();</span>
            <span>while</span> <span>(</span><span>size</span><span>--</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
                <span>TreeNode</span> <span>topNode</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
                <span>TreeNode</span> <span>parentNode</span> <span>=</span> <span>parentMap</span><span>.</span><span>get</span><span>(</span><span>topNode</span><span>);</span>
                <span>if</span> <span>(</span><span>parentNode</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>parentNode</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>parentNode</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>parentNode</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>left</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>right</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
            <span>}</span>
            <span>infectTime</span><span>++;</span>
        <span>}</span>
        <span>return</span> <span>infectTime</span> <span>-</span> <span>1</span><span>;</span>
    <span>}</span>
    <span>private</span> <span>TreeNode</span> <span>findParentAndTargetNode</span><span>(</span><span>TreeNode</span> <span>node</span><span>,</span> <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span><span>,</span> <span>int</span> <span>start</span><span>)</span> <span>{</span>
        <span>TreeNode</span> <span>targetNode</span> <span>=</span> <span>null</span><span>;</span>
        <span>Queue</span><span><</span><span>TreeNode</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>node</span><span>);</span>
        <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>node</span><span>,</span> <span>null</span><span>);</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>size</span> <span>=</span> <span>queue</span><span>.</span><span>size</span><span>();</span>
            <span>while</span> <span>(</span><span>size</span><span>--</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
                <span>TreeNode</span> <span>topNode</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
                <span>if</span> <span>(</span><span>targetNode</span> <span>==</span> <span>null</span> <span>&&</span> <span>topNode</span><span>.</span><span>val</span> <span>==</span> <span>start</span><span>)</span> <span>{</span>
                    <span>targetNode</span> <span>=</span> <span>topNode</span><span>;</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>left</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>,</span> <span>topNode</span><span>);</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>);</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>right</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>,</span> <span>topNode</span><span>);</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>);</span>
                <span>}</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>targetNode</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>/** * 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; * } * } */</span>
<span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>int</span> <span>amountOfTime</span><span>(</span><span>TreeNode</span> <span>root</span><span>,</span> <span>int</span> <span>start</span><span>)</span> <span>{</span>
        <span>if</span> <span>(</span><span>root</span> <span>==</span> <span>null</span><span>)</span> <span>{</span>
            <span>return</span> <span>0</span><span>;</span>
        <span>}</span>
        <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span> <span>=</span> <span>new</span> <span>HashMap</span><span><>();</span>
        <span>TreeNode</span> <span>targetNode</span> <span>=</span> <span>findParentAndTargetNode</span><span>(</span><span>root</span><span>,</span> <span>parentMap</span><span>,</span> <span>start</span><span>);</span>
        <span>// this is added just to make sure we have a targetNode</span>
        <span>if</span> <span>(</span><span>targetNode</span> <span>==</span> <span>null</span><span>)</span> <span>{</span>
            <span>return</span> <span>0</span><span>;</span>
        <span>}</span>
        <span>return</span> <span>minimumTimeToInfect</span><span>(</span><span>targetNode</span><span>,</span> <span>parentMap</span><span>);</span>
    <span>}</span>

    <span>private</span> <span>int</span> <span>minimumTimeToInfect</span><span>(</span><span>TreeNode</span> <span>targetNode</span><span>,</span> <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span><span>)</span> <span>{</span>
        <span>Queue</span><span><</span><span>TreeNode</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>targetNode</span><span>);</span>
        <span>Set</span><span><</span><span>Integer</span><span>></span> <span>visited</span> <span>=</span> <span>new</span> <span>HashSet</span><span><>();</span>
        <span>visited</span><span>.</span><span>add</span><span>(</span><span>targetNode</span><span>.</span><span>val</span><span>);</span>
        <span>int</span> <span>infectTime</span> <span>=</span> <span>0</span><span>;</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>size</span> <span>=</span> <span>queue</span><span>.</span><span>size</span><span>();</span>
            <span>while</span> <span>(</span><span>size</span><span>--</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
                <span>TreeNode</span> <span>topNode</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
                <span>TreeNode</span> <span>parentNode</span> <span>=</span> <span>parentMap</span><span>.</span><span>get</span><span>(</span><span>topNode</span><span>);</span>
                <span>if</span> <span>(</span><span>parentNode</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>parentNode</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>parentNode</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>parentNode</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>left</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>right</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>if</span> <span>(!</span><span>visited</span><span>.</span><span>contains</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>.</span><span>val</span><span>))</span> <span>{</span>
                        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>);</span>
                        <span>visited</span><span>.</span><span>add</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>.</span><span>val</span><span>);</span>
                    <span>}</span>
                <span>}</span>
            <span>}</span>
            <span>infectTime</span><span>++;</span>
        <span>}</span>
        <span>return</span> <span>infectTime</span> <span>-</span> <span>1</span><span>;</span>
    <span>}</span>

    <span>private</span> <span>TreeNode</span> <span>findParentAndTargetNode</span><span>(</span><span>TreeNode</span> <span>node</span><span>,</span> <span>Map</span><span><</span><span>TreeNode</span><span>,</span> <span>TreeNode</span><span>></span> <span>parentMap</span><span>,</span> <span>int</span> <span>start</span><span>)</span> <span>{</span>
        <span>TreeNode</span> <span>targetNode</span> <span>=</span> <span>null</span><span>;</span>
        <span>Queue</span><span><</span><span>TreeNode</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>queue</span><span>.</span><span>offer</span><span>(</span><span>node</span><span>);</span>
        <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>node</span><span>,</span> <span>null</span><span>);</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>size</span> <span>=</span> <span>queue</span><span>.</span><span>size</span><span>();</span>
            <span>while</span> <span>(</span><span>size</span><span>--</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
                <span>TreeNode</span> <span>topNode</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
                <span>if</span> <span>(</span><span>targetNode</span> <span>==</span> <span>null</span> <span>&&</span> <span>topNode</span><span>.</span><span>val</span> <span>==</span> <span>start</span><span>)</span> <span>{</span>
                    <span>targetNode</span> <span>=</span> <span>topNode</span><span>;</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>left</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>,</span> <span>topNode</span><span>);</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>left</span><span>);</span>
                <span>}</span>
                <span>if</span> <span>(</span><span>topNode</span><span>.</span><span>right</span> <span>!=</span> <span>null</span><span>)</span> <span>{</span>
                    <span>parentMap</span><span>.</span><span>put</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>,</span> <span>topNode</span><span>);</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>topNode</span><span>.</span><span>right</span><span>);</span>
                <span>}</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>targetNode</span><span>;</span>
    <span>}</span>
<span>}</span>
/** * 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 {
    public int amountOfTime(TreeNode root, int start) {
        if (root == null) {
            return 0;
        }
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        TreeNode targetNode = findParentAndTargetNode(root, parentMap, start);
        // this is added just to make sure we have a targetNode
        if (targetNode == null) {
            return 0;
        }
        return minimumTimeToInfect(targetNode, parentMap);
    }

    private int minimumTimeToInfect(TreeNode targetNode, Map<TreeNode, TreeNode> parentMap) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(targetNode);
        Set<Integer> visited = new HashSet<>();
        visited.add(targetNode.val);
        int infectTime = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode topNode = queue.poll();
                TreeNode parentNode = parentMap.get(topNode);
                if (parentNode != null) {
                    if (!visited.contains(parentNode.val)) {
                        queue.offer(parentNode);
                        visited.add(parentNode.val);
                    }
                }
                if (topNode.left != null) {
                    if (!visited.contains(topNode.left.val)) {
                        queue.offer(topNode.left);
                        visited.add(topNode.left.val);
                    }
                }
                if (topNode.right != null) {
                    if (!visited.contains(topNode.right.val)) {
                        queue.offer(topNode.right);
                        visited.add(topNode.right.val);
                    }
                }
            }
            infectTime++;
        }
        return infectTime - 1;
    }

    private TreeNode findParentAndTargetNode(TreeNode node, Map<TreeNode, TreeNode> parentMap, int start) {
        TreeNode targetNode = null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        parentMap.put(node, null);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode topNode = queue.poll();
                if (targetNode == null && topNode.val == start) {
                    targetNode = topNode;
                }
                if (topNode.left != null) {
                    parentMap.put(topNode.left, topNode);
                    queue.offer(topNode.left);
                }
                if (topNode.right != null) {
                    parentMap.put(topNode.right, topNode);
                    queue.offer(topNode.right);
                }
            }
        }
        return targetNode;
    }
}

Enter fullscreen mode Exit fullscreen mode

原文链接：Leetcode 2385. Amount of Time for Binary Tree to Be Infected

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Java（EN）
# java# learning# algorithms# coding
喜欢就支持一下吧
点赞6 分享
Finger rift,twisted in the love.
如果你为着错过夕阳而哭泣，那么你就要错群星了
评论 抢沙发

请登录后发表评论

    暂无评论内容

文章目录
kity的头像-拾光赋
文章目录
今日剩余 5.5%
本周剩余 43.6%
本月剩余 43.5%
本年剩余 70.7%
最近评论
杀人蜂的头像-拾光赋

杀人蜂4天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
Finger rift,twisted in the love.
如果你为着错过夕阳而哭泣，那么你就要错群星了