수준별로 이진 트리를 정렬하기 위한 최소 작업 수

2471. 레벨별로 이진 트리를 정렬하기 위한 최소 작업 횟수

난이도:중

주제: 트리, 너비 우선 검색, 이진 트리

고유한 값을 가진 이진 트리의 루트가 제공됩니다.

한 번의 작업으로 동일한 레벨 두 개의 노드를 선택하고 해당 값을 교환할 수 있습니다.

각 수준의 값을 엄밀히 증가하는 순서로 정렬하는 데 필요한 최소 작업 수를 반환합니다.

노드의 레벨은 해당 노드와 루트 노드 사이의 경로를 따라 있는 에지 수입니다.

예 1:

• 입력: 루트 = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• 출력: 3
• 설명:
  • 4와 3을 바꿉니다. 2레벨은 [3,4]가 됩니다.
  • 7과 5를 바꿉니다. 3레벨은 [5,6,8,7]이 됩니다.
  • 8과 7을 바꿉니다. 3레벨은 [5,6,7,8]이 됩니다.
  • 3개의 연산을 사용했기 때문에 3개를 반환합니다.
  • 필요한 최소 연산 수는 3개임을 입증할 수 있습니다.

예 2:

• 입력: 루트 = [1,3,2,7,6,5,4]
• 출력: 3
• 설명:
  • 3과 2를 바꿉니다. 2레벨은 [2,3]이 됩니다.
  • 7과 4를 바꿉니다. 3레벨은 [4,6,5,7]이 됩니다.
  • 6과 5를 바꿉니다. 3레벨은 [4,5,6,7]이 됩니다.
  • 3개의 연산을 사용했기 때문에 3개를 반환합니다.
  • 필요한 최소 연산 수는 3개임을 입증할 수 있습니다.

예 3:

• 입력: 루트 = [1,2,3,4,5,6]
• 출력: 0
• 설명: 각 레벨은 이미 오름차순으로 정렬되어 있으므로 0을 반환합니다.

제약조건:

• 트리의 노드 수는 [1, 10⁵] 범위에 있습니다.
• 1 5
• 트리의 모든 값은 고유합니다.

힌트:

1. 가치를 수준별로 그룹화하고 각 그룹을 독립적으로 해결할 수 있습니다.
2. BFS를 수행하여 수준별로 값을 그룹화하세요.
3. 각 레벨의 배열을 정렬하기 위한 최소 스왑 개수를 찾아보세요.
4. 배열을 반복하는 동안 현재 요소를 확인하고, 올바른 인덱스에 없으면 해당 요소를 원래 있어야 하는 요소의 인덱스로 바꿉니다.

해결책:

문제는 이진 트리의 값을 최소한의 연산 횟수로 엄격한 오름차순으로 레벨별로 정렬하는 것입니다. 각 작업에서 동일한 레벨에 있는 두 노드의 값을 교환할 수 있습니다. 목표는 정렬된 순서를 달성하는 데 필요한 최소 작업 수를 결정하는 것입니다.

핵심 포인트:

1. 이진 트리 수준: 이진 트리의 각 수준에는 엄격한 오름차순으로 정렬된 값이 있어야 합니다.
2. 고유 값: 모든 노드에는 고유 값이 있으므로 중복이 없으므로 정렬이 더 쉽습니다.
3. 레벨 그룹화를 위한 BFS: 너비 우선 검색(BFS)을 사용하여 트리를 탐색하고 레벨별로 노드를 그룹화합니다.
4. 최소 스왑: 각 레벨에 대해 해당 레벨에서 노드 값을 정렬하는 데 필요한 최소 스왑 수를 찾아야 합니다.
5. 제약조건: 트리는 최대 10^5개의 노드를 가질 수 있으므로 솔루션은 효율적이어야 합니다.

접근하다:

1. BFS 순회: BFS를 수행하여 트리를 순회하고 각 수준의 노드 값을 수집합니다.
2. 각 레벨 정렬: 각 레벨에 대해 최소 스왑 수를 계산하여 값을 엄격하게 오름차순으로 정렬합니다.
3. 주기 분해: 스왑을 최소화하기 위한 주요 관찰은 배열 정렬이 사이클에서 요소를 스왑하는 것으로 볼 수 있다는 것입니다. 잘못 배치된 요소의 각 주기에 대한 최소 스왑 횟수는 주기 길이에서 1을 뺀 값입니다.
4. 스왑 누적: 각 레벨의 스왑을 합산하여 필요한 총 스왑 수를 구합니다.

계획:

1. BFS: BFS를 사용하여 트리를 탐색하여 각 수준에서 노드를 수집합니다.
2. 각 레벨 정렬: 각 레벨의 값을 정렬하고 최소 스왑 수를 계산합니다.
3. 스왑 계산: 주기 분해를 사용하여 각 수준에서 노드를 정렬하는 데 필요한 최소 스왑을 찾습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2471. 이진 트리를 수준별로 정렬하기 위한 최소 작업 횟수

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

설명:

1. 1단계: BFS를 수행하여 수준별로 노드를 그룹화합니다:

   • 루트에서 시작하여 레벨별로 트리 레벨을 탐색합니다.
   • 각 노드에 대해 레벨 배열의 해당 레벨에 해당 값을 추가합니다.

2. 2단계: 각 레벨에 대해 최소 스왑을 계산하여 값을 정렬합니다:

   • 각 수준의 값을 정렬합니다.
   • 주기 기반 접근 방식을 사용하여 현재 레벨을 정렬된 레벨로 변환하는 데 필요한 최소 스왑을 계산합니다.

3. 주기 분해:

   • 정렬되지 않은 각 요소에 대해 주기(즉, 어디로 가야 하는지)를 추적하고 요소를 방문한 것으로 표시합니다.
   • 각 주기마다 필요한 교체 횟수는 주기 길이에서 1을 뺀 값입니다.

4. 총 스왑 횟수 반환:

   • 각 레벨에 필요한 스왑을 합산하여 그 합계를 반환합니다.

예제 연습:

예시 1:

입력 트리:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

레벨:

• 레벨 0: [1]
• 레벨 1: [4, 3]
• 레벨 2: [7, 6, 8, 5]
• 레벨 3: [9, 10]

1. 레벨 1: [4, 3]

   • 1개의 스왑(4와 3 스왑)을 사용하여 [3, 4]로 정렬합니다.

2. 레벨 2: [7, 6, 8, 5]

   • 2개의 스왑(7과 5 스왑, 8과 7 스왑)을 사용하여 [5, 6, 7, 8]로 정렬합니다.

3. 레벨 3: [9, 10]

   • 이미 정렬되었으므로 교체가 필요하지 않습니다.

총 스왑 = 1(레벨 1) 2(레벨 2) = 3 스왑

출력: 3

예 2:

입력 트리:

        1
       / \
      4   3
     / \ / \
    7  6 8  5
             \
              9
               \
                10

레벨:

• 레벨 0: [1]
• 레벨 1: [3, 2]
• 레벨 2: [7, 6, 5, 4]

1. 레벨 1: [3, 2]

   • 1개의 스왑을 사용하여 [2, 3]으로 정렬합니다(3과 2 스왑).

2. 레벨 2: [7, 6, 5, 4]

   • 2개의 스왑(7과 4 교환, 6과 5 교환)을 사용하여 [4, 5, 6, 7]로 정렬합니다.

총 스왑 = 1(레벨 1) 2(레벨 2) = 3 스왑

출력: 3

시간 복잡도:

1. BFS: O(N) 여기서 N은 트리의 노드 수입니다.
2. 각 레벨 정렬: 각 레벨의 값을 정렬하려면 O(L log L)이 필요합니다. 여기서 L은 현재 레벨의 노드 수. 최악의 경우 전체 정렬 복잡도는 O(N log N)입니다.
3. 주기 분해: O(L) 각 레벨

따라서 전체 시간 복잡도는 O(N log N)이며, 이는 제약 조건을 고려하면 충분히 효율적입니다.

예를 들어 출력:

입력 트리의 경우:

<?php /**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

예제에 자세히 설명된 대로 출력은 3개의 스왑입니다.

이 솔루션은 BFS를 사용하여 레벨 및 사이클 분해별로 노드를 그룹화하여 스왑 수를 최소화함으로써 이진 트리의 각 레벨을 정렬하는 데 필요한 최소 스왑 수를 효율적으로 계산합니다. O(N log N)의 시간 복잡도는 최대 10^5개 노드

가 있는 트리를 처리하는 데 최적입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 수준별로 이진 트리를 정렬하기 위한 최소 작업 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!