수준별로 이진 트리를 정렬하기 위한 최소 작업 수-PHP 튜토리얼-php.cn

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

Mary-Kate Olsen

풀어 주다： 2025-01-03 02:42:37

원래의

646명이 탐색했습니다.

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

난이도:중

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

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

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

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

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

예 1:

Minimum Number of Operations to Sort a Binary Tree by Level

입력: 루트 = [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:

Minimum Number of Operations to Sort a Binary Tree by Level

입력: 루트 = [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:

Minimum Number of Operations to Sort a Binary Tree by Level

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

제약조건:

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

힌트:

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

해결책:

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

핵심 포인트:

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

접근하다:

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

계획:

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

이 솔루션을 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
     */
}
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li>
<p><strong>1단계: BFS를 수행하여 수준별로 노드를 그룹화합니다</strong>:</p>
<ul>
<li>루트에서 시작하여 레벨별로 트리 레벨을 탐색합니다.</li>
<li>각 노드에 대해 레벨 배열의 해당 레벨에 해당 값을 추가합니다.</li>
</ul>
</li>
<li>
<p><strong>2단계: 각 레벨에 대해 최소 스왑을 계산하여 값을 정렬합니다</strong>:</p>

<ul>
<li>각 수준의 값을 정렬합니다.</li>
<li>주기 기반 접근 방식을 사용하여 현재 레벨을 정렬된 레벨로 변환하는 데 필요한 최소 스왑을 계산합니다.</li>
</ul>
</li>
<li>
<p><strong>주기 분해</strong>:</p>

<ul>
<li>정렬되지 않은 각 요소에 대해 주기(즉, 어디로 가야 하는지)를 추적하고 요소를 방문한 것으로 표시합니다.</li>
<li>각 주기마다 필요한 교체 횟수는 주기 길이에서 1을 뺀 값입니다.</li>
</ul>
</li>
<li>
<p><strong>총 스왑 횟수 반환</strong>:</p>

<ul>
<li>각 레벨에 필요한 스왑을 합산하여 그 합계를 반환합니다.</li>
</ul>
</li>
</ol>

<h3>
  
  
  예제 연습:
</h3>

<h4>
  
  
  예시 1:
</h4>

<p>입력 트리:<br>
</p>

<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false"><?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
     */
}
?>

로그인 후 복사

예 2:

시간 복잡도:

따라서 전체 시간 복잡도는 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 */ } ?>

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

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

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