이진 트리에서 K번째로 큰 합계

2583. 이진 트리에서 K번째로 큰 합

난이도:중

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

이진 트리의 루트와 양의 정수 k가 주어졌습니다.

트리의 레벨 합계는 동일레벨

에 있는 노드 값의 합계입니다.

트리에서 k^번째 가장 큰 수준 합계를 반환합니다(반드시 별개일 필요는 없음). 트리의 수준이 k보다 적으면 -1을 반환합니다.

참고 두 노드가 루트로부터 동일한 거리에 있으면 동일한 레벨에 있습니다.

예 1:

• 입력: 루트 = [5,8,9,2,1,3,7,4,6], k = 2
• 출력: 13
• 설명: 레벨 합계는 다음과 같습니다.
  • 레벨 1: 5.
  • 레벨 2: 8 9 = 17.
  • 레벨 3: 2 1 3 7 = 13.
  • 레벨 4: 4 6 = 10.
  • 두 번째 가장 큰 수준의 합은 13입니다.

예 2:

• 입력: 루트 = [1,2,null,3], k = 1
• 출력: 3
• 설명: 최대 레벨 합은 3입니다.

제약조건:

• 트리의 노드 수는 n개입니다.
• 2 5
• 1 <= Node.val <= 10⁶
• 1 <= k <= n

힌트:

1. 각 레벨의 노드 값의 합을 구하고 k번째로 큰 값을 반환합니다.
2. 각 레벨의 노드 값의 합을 찾으려면 DFS 또는 BFS 알고리즘을 사용하여 트리를 순회하고 각 노드의 레벨을 추적할 수 있습니다.

해결책:

다음 단계를 따르세요.

1. 레벨 순서 탐색: 너비 우선 검색(BFS)을 사용하여 트리 레벨을 레벨별로 탐색합니다.
2. 레벨 합계 계산: BFS 순회 중에 각 레벨의 노드 값 합계를 계산합니다.
3. k번째로 큰 합계 정렬 및 찾기: 모든 수준에 대한 합계를 계산한 후 합계를 정렬하고 k번째로 큰 값을 검색합니다.

이 솔루션을 PHP: 2583으로 구현해 보겠습니다. 이진 트리에서 K번째로 큰 합

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>





  
  
  설명:



TreeNode 클래스: 이진 트리의 노드를 나타내기 위해 TreeNode 클래스를 정의합니다. 여기서 각 노드에는 값(val), 왼쪽 자식(왼쪽) 및 오른쪽 자식이 있습니다. (오른쪽).
BFS 순회: kthLargestLevelSum 함수는 대기열을 사용하여 BFS 순회를 수행합니다. 각 레벨에 대해 노드 값을 합산하고 그 결과를 배열($levelSums)에 저장합니다.
레벨 합계 정렬: 전체 트리를 탐색하고 레벨 합계를 계산한 후 rsort를 사용하여 합계를 내림차순으로 정렬합니다. 이를 통해 k번째로 큰 합계에 쉽게 접근할 수 있습니다.
Edge Case Handling: k 수준보다 적으면 -1을 반환합니다.



  
  
  시간 복잡도:




BFS 순회: O(n), 여기서 n은 트리의 노드 수입니다.

정렬: O(m log m), 여기서 m은 트리의 수준 수입니다. m이 n보다 훨씬 작기 때문에 정렬이 비교적 빠릅니다.
전체 시간 복잡도: O(n·m·log·m).



  
  
  공간 복잡도:




Queue: O(n), BFS 동안 노드를 저장합니다.

레벨 합계: O(m), 각 레벨의 합계를 저장합니다.
전체 공간 복잡도: O(n).


이 접근 방식을 사용하면 트리를 효율적으로 탐색하고 올바른 k번째 가장 큰 수준 합계
를 반환할 수 있습니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 이진 트리에서 K번째로 큰 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!