[LeetCode#310] Minimum Height Trees

2024. 9. 24. 17:21·Algorithm/문제풀이

 

❒ Description


날짜 2024.09.23 (월)
레벨 Medium
제목 Minimum Height Trees
링크 https://leetcode.com/problems/minimum-height-trees/description/
자료구조 그래프
시간복잡도 O(N)

 

 

 

 

 

❒ 문제 분석


이 문제는 트리의 리프 노드에서부터 루트로 다가가며 해결해야 한다. 여기서는 차수가 1인 리프노드를 제거

하면서 루트로 다가가야 한다. 가장 낮은  차수를 제거하는 방식은 위상 정렬과 유사한 방식으로 해석할 수 있다.

 

※ 차수(degree) : 각 노드가 가진 서브트리의 갯수

 

 

 

 

❒ Solution


1. 리프노드를 제거하는 방법

더보기
더보기
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    // 예외 처리
    if (n == 1) return List.of(0);

    // 1. 차수관리를 위해 degree 배열 생성
    int[] degrees = new int[n];

    // 2. 그래프를 인접리스트로 표현
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
        // 3. degrees 배열도 같이 update
        degrees[edge[0]]++;
        degrees[edge[1]]++;
    }
    
    // 4. Q생성 후 차수가 1인 노드들 삽입.
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (degrees[i] == 1) q.offer(i);
    } 	
    
    // 5. 노드가 2개 이하로 남을 때 까지 반복
    while (n > 2) {
        // 6. 최초에 삽입된 차수가 1인 리프노드 갯수 빼기 
        int qSize = q.size();
        n -= qSize;
        for (int i = 0; i < size; i++) {
            int node = q.poll();
            for (int k : graph.get(node)) {
                degrees[k]--;
                if (degrees[k] == 1) {
                    q.add(k);
                }
            }
        }
    }
    
    return new ArrayList<>(q);
}
while (n > 2) {
    int qSize = q.size();
    n -= qSize;
    for (int i = 0; i < size; i++) {
        int node = q.poll();
        for (int k : graph.get(node)) {
            degrees[k]--;
            if (degrees[k] == 1) {
                q.add(k);
            }
        }
    }
}
  • 양방향 그래프이기 때문에 for문(i)을 순회
  • 새로운 리프노드가 생기면(차수가 1이 되면) q에 삽입
  • `n -= qSize` : 현재 q에 있는 갯수만큼 노드를 제거

 

2. 재귀를 통한 풀이 (Time Limit Exceeded)

더보기
더보기
public class V1 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 결과 배열
        List<Integer> result = new ArrayList<>();
        if (n == 1) {
            result.add(0);
            return result;
        }
        // 최소 높이
        int lowest = Integer.MAX_VALUE;
        // edges 배열 to map
        Map<Integer, List<Integer> > graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new LinkedList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        // main logic
        for (int i = 0; i < n; i++) {
            int height = depth(graph, i, -1);
            if (height < lowest) {
                lowest = height;
                result.clear();
                result.add(i);
            } else if (height == lowest) {
                result.add(i);
            }
        }
        return result;
    }

    private int depth(Map<Integer, List<Integer>> graph, int root, int prev) {
        int depth = -1;
        List<Integer> nextNodes = graph.get(root);
        for (Integer nextNode : nextNodes) {
            if (nextNode != prev) {
                depth = Math.max(depth, depth(graph, nextNode, root));
            }
        }
        depth++;
        return depth;
    }
}

위 코드는 Time Limit Exceeded 에러가 발생하는 코드이다.

 

 

 

 


 

'Algorithm > 문제풀이' 카테고리의 다른 글

[LeetCode#1038] Binary Search Tree to Greater Sum Tree  (0) 2024.09.25
[LeetCode#108] Convert Sorted Array to Binary Search Tree  (0) 2024.09.25
[LeetCode#110] Balanced Binary Tree  (0) 2024.09.23
[LeetCode#] Invert Binary Tree  (0) 2024.09.22
[LeetCode#687] Longest Univalue Path  (0) 2024.09.21
'Algorithm/문제풀이' 카테고리의 다른 글
  • [LeetCode#1038] Binary Search Tree to Greater Sum Tree
  • [LeetCode#108] Convert Sorted Array to Binary Search Tree
  • [LeetCode#110] Balanced Binary Tree
  • [LeetCode#] Invert Binary Tree
gilbert9172
gilbert9172
gilbert9172 님의 블로그 입니다.
  • gilbert9172
    バックエンド
    gilbert9172
  • 전체
    오늘
    어제
    • All Categories (167)
      • 우테코 7기 (21)
        • 1주차 (8)
        • 2주차 (5)
        • 3주차 (6)
      • Langauge (4)
        • Java (3)
        • Kotlin (1)
      • Back-End (13)
        • SpringBoot (1)
        • Trouble Shooting (0)
        • Setup & Configuration (1)
        • SQL (3)
        • Redis (8)
      • Architecture (6)
        • Multi Module (1)
        • DDD (5)
      • CS (30)
        • Data Structure (6)
        • Operating System (0)
        • Network (12)
        • Database (10)
        • Design Pattern (2)
      • Algorithm (78)
        • 내용 정리 (18)
        • 문제풀이 (60)
      • DevOps (6)
        • AWS (5)
        • Git (1)
      • Front-End (1)
        • Trouble Shooting (1)
      • Project (6)
        • 페이스콕 (6)
      • Book (1)
        • 이벤트 기반 마이크로서비스 구축 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    부분단조성
    binarysearch
    오블완
    Back-Tracking
    sliding-window
    Two-Pointer
    greedy
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
gilbert9172
[LeetCode#310] Minimum Height Trees
상단으로

티스토리툴바