2385. Amount of Time for Binary Tree to Be Infected

• 트리의 특정 지점에서 감염이 시작되어 트리 전체로 퍼져나가는 시간을 구한다.
• 시작 시점 0 에 해당 지점이 이미 감염된 상태이다.
• 매 시간 1 마다 인접한 노드가 감염된다.

• 문제를 한마디로 요약하면 트리의 특정 지점을 root로 하여 leaf 노드로 도달하는 최대 깊이를 구하는 것이다.

• 트리의 특정 지점을 root로 바꾸어야 하기에 트리를 그래프로 변환 (또는 트리를 재구성)하여 풀어야 한다.
• 이렇게 하려면 추가적으로 메모리 공간이 필요하다.

• 하지만 상태값을 이용하여 푸는 방법도 있다.
• 현재 노드를 포함하여 경로의 최대 길이를 구한뒤 마지막에 -1을 하여 결과를 도출해낸다.
• 시작점은 이미 감염 되었기 때문에 시간에서 1을 빼야 한다.
• 트리를 순회할 때 매 단계마다 두 값을 도출해낸다.
• 값1: 현재 트리에서 구할 수 있는 최대 경로의 길이
• 값2: 감염 시작점에서 현재 지점까지의 거리 (감염 시작점을 포함하며, 감염이 없으면 0이 된다)
• 순회는 다음과 같이 이루어진다.
• 왼쪽, 오른쪽 각각을 순회하여 결과값 left, right 을 도출해낸다.
• 양쪽 모두 감염이 없다면
• 값1: 양쪽 트리 중 최대 깊이 값 max(left.getKey(), right.getKey()) 을 구한뒤 1을 더한다
• 값2: 현재 노드가 감염 시작점이라면 1, 아니라면 0을 돌려준다
• 왼쪽, 오른쪽 중 어느 한쪽이 감염되었다면
• 감염된 쪽을 A, 감염되지 않은 쪽은 B라고 할 때
• 값1
• A 쪽의 깊이는 결과값 A.getKey() 그대로가 된다.
• 반면 B 쪽은 감염 시작점 ~ 현재 노드까지의 거리 + B 쪽의 트리 깊이가 감염 거리가 되므로 최종 깊이 값은 (B.getKey() + 1) + A.getValue() 가 된다.
• 두 값 중에 큰 값을 결과로 한다.
• 값2
• A 쪽의 감염 거리에 1을 더한다 (이제 현재 트리가 감염된 트리가 된다).

/**
 * 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 {
    static final Pair<Integer, Integer> ZERO = new Pair<Integer, Integer>(0, 0);

    Pair<Integer, Integer> traverse(TreeNode node, int start) {
        Pair<Integer, Integer> left = node.left != null? 
            traverse(node.left, start) : ZERO;
        Pair<Integer, Integer> right = node.right != null?
            traverse(node.right, start) : ZERO;
        if (left.getValue() == 0 && right.getValue() == 0) {
            int depth = Math.max(left.getKey(), right.getKey()) + 1;
            return new Pair(depth, node.val == start? 1 : 0);
        } else if (left.getValue() != 0) {
            return new Pair(
                Math.max(left.getKey(), right.getKey() + 1 + left.getValue()),
                left.getValue() + 1
            );
        } else {
            int x = Math.max(right.getKey() + 1, left.getKey() + right.getValue());
            return new Pair(
                Math.max(right.getKey(), left.getKey() + 1 + right.getValue()),
                right.getValue() + 1
            );
        }
    }

    public int amountOfTime(TreeNode root, int start) {
        Pair<Integer, Integer> result = traverse(root, start);
        return result.getKey() - 1;
    }
}