[LeetCode 687] Longest Univalue Path (Java)

🚀 문제 분석

• 목표: 트리의 노드 중 동일한 값을 가진 노드들로 연결된 가장 긴 경로의 길이를 구합니다.
• 핵심: 경로는 한 노드에서 시작해 다른 노드로 끝나는 형태이며, 반드시 루트를 지날 필요는 없습니다.
• 전략: 후위 순회(Post-order Traversal)를 이용해 자식 노드에서 올라온 정보를 바탕으로 현재 노드에서의 최댓값을 갱신합니다.

💡 해결 전략: Bottom-up 재귀

트리 문제를 풀 때 가장 중요한 것은 "현재 노드가 부모에게 전달해야 할 정보는 무엇인가?"를 결정하는 것입니다.

1. 자식의 보고: 각 노드는 자식 노드로부터 해당 방향으로 뻗어 나갈 수 있는 '동일 값 경로의 최대 길이'를 보고받습니다.
2. 연결 확인:
   • 왼쪽 자식과 내 값이 같다면? 왼쪽 자식의 보고 + 1
   • 오른쪽 자식과 내 값이 같다면? 오른쪽 자식의 보고 + 1
   • 다르다면? 해당 방향의 길이는 0입니다.
3. 최댓값 갱신 (answer): 현재 노드를 '정점'으로 삼아 왼쪽 경로와 오른쪽 경로를 합친 값이 전체 최댓값(answer)보다 크다면 갱신합니다.
4. 부모에게 보고: 부모 노드 입장에서는 나를 거쳐 왼쪽이나 오른쪽 한 방향으로만 갈 수 있으므로, Math.max(leftPath, rightPath)를 리턴합니다.

💻 구현 코드 (Java)

class Solution {
    int answer;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return answer;
    }

    int dfs(TreeNode node) {
        if (node == null) return 0;

        // 1. 하위 노드로부터 정보 수집 (Bottom-up)
        int left = dfs(node.left);
        int right = dfs(node.right);

        int leftPath = 0;
        int rightPath = 0;

        // 2. 현재 노드와 자식 노드의 값 비교 및 경로 확장
        if (node.left != null && node.left.val == node.val) {
            leftPath = left + 1;
        }

        if (node.right != null && node.right.val == node.val) {
            rightPath = right + 1;
        }

        // 3. 현재 노드를 정점으로 하는 '좌+우' 경로로 최댓값 갱신
        answer = Math.max(answer, leftPath + rightPath);

        // 4. 부모 노드에게는 한쪽 방향의 최댓값만 전달
        return Math.max(leftPath, rightPath);
    }
}

🧐 기술적 고찰

• 전역 변수 활용: answer를 필드 변수로 두어 재귀 과정 중 어느 위치에서든 최댓값이 발견되면 즉시 반영될 수 있도록 설계되었습니다.
• 상태 분리: answer를 갱신하는 식(leftPath + rightPath)과 return하는 식(max(leftPath, rightPath))이 다르다는 점이 이 문제의 가장 높은 허들인데, 이를 깔끔하게 분리하셨습니다.
• 시간 복잡도: 모든 노드를 한 번씩 방문하므로 $O(N)$에 해결됩니다. 공간 복잡도는 트리의 높이만큼 스택이 쌓이므로 $O(H)$입니다.