. 각 트리 행에서 가장 큰 값 찾기

515. 각 트리 행에서 가장 큰 값 찾기

난이도:중

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

이진 트리의 루트가 주어지면 트리의 각 행에서 가장 큰 값의 배열을 반환합니다(0-인덱스).

예 1:

• 입력: 루트 = [1,3,2,5,3,null,9]
• 출력: [1,3,9]

예 2:

• 입력: 루트 = [1,2,3]
• 출력: [1,3]

제약조건:

• 트리의 노드 수는 [0, 10⁴] 범위에 있습니다.
• -2³¹ <= Node.val <= 2³¹ - 1

해결책:

"각 트리 행에서 가장 큰 값 찾기" 문제는 이진 트리의 각 수준(행)에 존재하는 가장 큰 값을 식별해야 합니다. 이진 트리가 주어지면 목표는 트리를 행별로 순회하여 각 행에서 최대값을 수집하는 것입니다. 이 문제는 BFS(너비 우선 검색) 또는 DFS(깊이 우선 검색)

과 같은 기본적인 트리 탐색 기술과 관련이 있습니다.

핵심사항

1. 트리 순회: 이진 트리의 모든 수준을 순회하여 각 수준에서 가장 큰 값을 식별하는 솔루션이 포함됩니다.
2. BFS(너비 우선 검색): BFS는 레벨별 순회에 적합하므로 각 행에서 가장 큰 값을 간단하게 찾을 수 있습니다.
3. 제약조건: 빈 트리 및 제약 조건 범위 내에서 크거나 작은 정수 값을 갖는 노드와 같은 극단적인 경우를 처리합니다.

접근방법

각 행에서 가장 큰 값을 찾는 가장 간단한 접근 방식은 BFS:

를 사용하는 것입니다.

• 레벨별로 트리를 탐색하세요.
• 각 레벨마다 가장 큰 값을 추적하세요.

또는 DFS를 사용할 수도 있습니다.

• 트리를 재귀적으로 순회하며 각 깊이의 최대값 기록을 유지합니다.

계획

1. 각 행의 가장 큰 값을 저장하도록 배열을 초기화합니다.
2. BFS 순회를 위해 대기열을 사용합니다.
   • 루트 노드부터 시작하세요.
   • 다음 레벨로 이동하기 전에 현재 레벨의 모든 노드를 처리합니다.
3. 각 레벨:
   • 모든 노드를 반복하여 최대값을 찾습니다.
   • 이 값을 결과 배열에 추가하세요.
4. 순회 완료 후 결과 배열을 반환합니다.

해결 단계

1. 입력 확인: 루트가 null인 경우 빈 배열을 반환합니다.
2. BFS 설정:
   • 루트 노드로 초기화된 대기열을 사용하세요.
   • 빈 결과 배열을 초기화합니다.
3. 트래버스 레벨:
   • 각 레벨의 최대값을 추적하세요.
   • 다음 레벨 대기열에 하위 노드를 추가합니다.
4. 결과 업데이트:
   • 각 레벨의 최대값을 결과 배열에 추가합니다.
5. 결과 반환: 각 행에 대해 가장 큰 값을 포함하는 결과 배열을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 515. 각 트리 행에서 가장 큰 값 찾기

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

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>





  
  
  설명:



  
  
  입력: [1,3,2,5,3,널,9]




레벨 0: 노드 값: [1] → 최대값: 1.

레벨 1: 노드 값: [3, 2] → 최대값: 3.

레벨 2: 노드 값: [5, 3, 9] → 최대: 9.
#### 출력: [1, 3, 9].



  
  
  시간복잡도




BFS Traversal: 각 노드를 한 번씩 처리 → O(n).

최대값 찾기: 순회 중에 완료 → 레벨당 O(1).

합계: O(n).



  
  
  공간 복잡도




Queue Storage: 최대 트리 너비(가장 큰 수준의 노드 수) → O(w) 여기서 w는 트리의 최대 너비입니다.



  
  
  예시 출력


입력: 루트 = [1,3,2,5,3,null,9]


출력: [1, 3, 9].

이 BFS 기반 솔루션은 선형 시간 복잡도를 사용하여 각 트리 행에서 가장 큰 값을 효율적으로 계산합니다. 큰 나무, 음수 값, 빈 나무와 같은 엣지 케이스를 효과적으로 처리합니다.

연락처 링크

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

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

링크드인
깃허브



          

            
  

            
        
위 내용은 . 각 트리 행에서 가장 큰 값 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!