_2385. Amount of Time for Binary Tree to Be Infected.md

2385. Amount of Time for Binary Tree to Be Infected

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 26, 2024

Last updated : June 26, 2024

---

Related Topics : Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 62.86 %

---

Solutions

• m2385.py

Python

m2385.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        self.output:int = 0

        def infectDecendents(curr: Optional[TreeNode], time: int) -> None :
            self.output = max(self.output, time)

            time += 1
            if curr.left :
                infectDecendents(curr.left, time)
            if curr.right :
                infectDecendents(curr.right, time)

        def infectUpwards(curr: Optional[TreeNode]) -> int :
            if not curr :
                return 0

            if curr.val == start :
                if curr.left :
                    infectDecendents(curr.left, 1)
                if curr.right :
                    infectDecendents(curr.right, 1)
                return 1
            
            left = infectUpwards(curr.left)
            right = infectUpwards(curr.right)
            maxx = max(left, right)
            
            if maxx == 0 :
                return 0

            self.output = max(self.output, maxx)
            
            maxx += 1
            if left == 0 and curr.left :
                infectDecendents(curr.left, maxx)
            elif right == 0 and curr.right :
                infectDecendents(curr.right, maxx)
            
            return maxx

        infectUpwards(root)

        return self.output