⭐ 문제

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/?envType=daily-question&envId=2024-07-18

🧐 시도

class Solution {
int count = 0;

public int countPairs(TreeNode root, int distance) {
    dfs(root, distance);
    return count;
}

private List<Integer> dfs(TreeNode node, int distance) {
    if (node == null) {
        return new ArrayList<>();
    }
    
    if (node.left == null && node.right == null) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        return list;
    }
    
    List<Integer> leftList = dfs(node.left, distance);
    List<Integer> rightList = dfs(node.right, distance);
    
    for (int left : leftList) {
        for (int right : rightList) {
            if (left + right <= distance) {
                count++;
            }
        }
    }
    
    List<Integer> list = new ArrayList<>();
    for (int i : leftList) {
        if (i + 1 < distance) {
            list.add(i + 1);
        }
    }
    for (int i : rightList) {
        if (i + 1 < distance) {
            list.add(i + 1);
        }
    }
    
    return list;
}

}

📝 리뷰

countPairs 메소드는 주어진 루트 노드와 거리를 입력받아 dfs 메소드를 호출합니다.
dfs 메소드는 깊이 우선 탐색(DFS)을 수행하며 다음과 같이 작동합니다:

노드가 null이면 빈 리스트를 반환합니다.
노드가 리프 노드(자식이 없는 노드)면 [1]을 포함하는 리스트를 반환합니다.
왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 dfs를 호출합니다.
왼쪽 리스트와 오른쪽 리스트의 모든 조합에 대해 거리를 확인하고, 조건을 만족하면 count를 증가시킵니다.
현재 노드에서의 거리 정보를 포함하는 새 리스트를 생성하여 반환합니다.

최종적으로 count에 저장된 값이 조건을 만족하는 노드 쌍의 개수입니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 트리의 노드 수입니다. 각 노드를 한 번씩 방문하기 때문입니다.