2458. 하위 트리 제거 쿼리 후 이진 트리 높이
난이도:어려움
주제: 배열, 트리, 깊이 우선 검색, 너비 우선 검색, 이진 트리
n개의 노드가 있는 이진 트리의 루트가 제공됩니다. 각 노드에는 1부터 n까지 고유한 값이 할당됩니다. 또한 m 크기의 배열 쿼리가 제공됩니다.
i번째 쿼리에서 다음을 수행하는 트리에서 m 독립 쿼리를 수행해야 합니다.
-
트리에서 query[i] 값을 가진 노드를 루트로 하는 하위 트리를 제거합니다. 쿼리[i]가 루트 값과 같지 보장합니다.
크기가 m인 배열 응답을 반환합니다. 여기서 응답[i]는 i번째 쿼리를 수행한 후 트리의 높이입니다.
참고:
- 쿼리는 독립적이므로 각 쿼리 후에 트리는 초기 상태로 돌아갑니다.
- 트리의 높이는 루트에서 트리의 일부 노드까지의 가장 긴 단순 경로에 있는 가장자리 수입니다.
예 1:
-
입력: 루트 = [1,3,4,2,null,6,5,null,null,null,null,null,7], 쿼리 = [4]
-
출력: [2]
-
설명: 위 다이어그램은 값이 4인 노드를 루트로 하는 하위 트리를 제거한 후의 트리를 보여줍니다.
- 트리의 높이는 2입니다(경로 1 -> 3 -> 2).
예 2:
-
입력: 루트 = [5,8,9,2,1,3,7,4,6], 쿼리 = [3,2,4,8]
-
출력: [3,2,3,2]
-
설명: 다음과 같은 쿼리가 있습니다.
- 값이 3인 노드를 루트로 하는 하위 트리를 제거합니다. 트리의 높이는 3이 됩니다(경로 5 -> 8 -> 2 -> 4).
- 값이 2인 노드를 루트로 하는 하위 트리를 제거합니다. 트리의 높이는 2가 됩니다(경로 5 -> 8 -> 1).
- 값이 4인 노드를 루트로 하는 하위 트리를 제거합니다. 트리의 높이는 3이 됩니다(경로 5 -> 8 -> 2 -> 6).
- 값이 8인 노드를 루트로 하는 하위 트리를 제거하면 트리의 높이가 2가 됩니다(경로 5 -> 9 -> 3).
제약조건:
- 트리의 노드 수는 n개입니다.
- 2 5
- 1 <= Node.val <= n
- 트리의 모든 값은 고유합니다.
- m == 쿼리 길이
- 1 4)
- 1 <= 쿼리[i] <= n
- 쿼리[i] != root.val
힌트:
- 1부터 n까지 각 노드에 대한 답을 미리 계산하고 각 쿼리에 O(1)로 답해 보세요.
- 각 하위 트리의 높이를 계산한 후 단일 트리 순회에서 답변을 미리 계산할 수 있습니다.
해결책:
이 솔루션은 2단계 접근 방식을 사용합니다.
-
트리에서 각 노드의 높이를 계산합니다.
-
쿼리된 각 노드에 루트가 있는 하위 트리를 제거한 후 트리의 최대 높이를 결정합니다.
PHP에서 이 솔루션을 구현해 보겠습니다: 2458. 하위 트리 제거 쿼리 후 이진 트리 높이
코드 분석
1. 클래스 정의 및 속성:
class Solution {
private $valToMaxHeight = [];
private $valToHeight = [];
로그인 후 복사
로그인 후 복사
-
valToMaxHeight: 이 배열은 각 노드의 하위 트리를 제거한 후 트리의 최대 높이를 저장합니다.
-
valToHeight: 이 배열은 각 노드의 하위 트리 높이를 저장합니다.
2. 주요 기능:
function treeQueries($root, $queries) {
...
...
...
/**
* go to ./solution.php
*/
}
로그인 후 복사
로그인 후 복사
- treeQueries 함수는 트리의 루트와 쿼리 배열을 가져옵니다.
- 먼저 높이 함수를 호출하여 각 노드의 높이를 계산합니다.
- 그런 다음 dfs(깊이 우선 검색) 함수를 호출하여 하위 트리 제거 후 최대 높이를 계산합니다.
- 마지막으로 각 쿼리의 결과로 답변 배열을 채웁니다.
3. 높이 계산:
private function height($node) {
...
...
...
/**
* go to ./solution.php
*/
}
로그인 후 복사
- 이 함수는 각 노드의 높이를 재귀적으로 계산합니다.
- 노드가 null이면 0을 반환합니다.
- 노드의 높이가 이미 계산된 경우 캐시(valToHeight)에서 이를 검색합니다.
- 왼쪽과 오른쪽 자식의 키를 기준으로 키를 계산하여 valToHeight에 저장합니다.
4. 최대 높이에 대한 깊이 우선 검색:
private function dfs($node, $depth, $maxHeight) {
...
...
...
/**
* go to ./solution.php
*/
}
로그인 후 복사
- 이 함수는 DFS를 수행하여 각 노드의 하위 트리가 제거된 후 트리의 최대 높이를 계산합니다.
- 현재 노드의 현재 최대 높이를 valToMaxHeight에 기록합니다.
- 왼쪽 및 오른쪽 하위 트리의 높이를 계산하고 그에 따라 최대 높이를 업데이트합니다.
- 왼쪽과 오른쪽 자식에 대해 자신을 재귀적으로 호출하여 깊이와 최대 높이를 업데이트합니다.
예제 연습
예제를 단계별로 살펴보겠습니다.
입력 예:
// Tree Structure
// 1
// / \
// 3 4
// / / \
// 2 6 5
// \
// 7
$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];
로그인 후 복사
초기 높이 계산:
- 1:3으로 뿌리를 내린 나무의 높이
- 뿌리나무의 높이는 3:2
- 4:2에 뿌리를 둔 트리의 높이(6과 5에 뿌리를 둔 하위 트리의 높이)
- 루트가 6:1인 트리의 높이(그냥 노드 7)
- 2:0(리프 노드)에 뿌리를 둔 트리의 높이
높이 계산 후 valToHeight는 다음과 같습니다.
class Solution {
private $valToMaxHeight = [];
private $valToHeight = [];
로그인 후 복사
로그인 후 복사
Max Heights용 DFS:
- 루트(1)의 경우 하위 트리 4개 잎을 제거합니다.
- 왼쪽 높이: 2(루트는 3)
- 오른쪽 높이: 1(루트는 5)
- 따라서 4를 제거한 후의 최대 높이는 2입니다.
쿼리 후 결과 배열:
최종 출력
제공된 입력의 결과는 다음과 같습니다.
function treeQueries($root, $queries) {
...
...
...
/**
* go to ./solution.php
*/
}
로그인 후 복사
로그인 후 복사
이 구조화된 접근 방식을 통해 필요한 높이를 효율적으로 계산하고 초기 전처리 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다. 전체 복잡도는 O(n·m)입니다. 여기서 n은 트리의 노드 수이고 입니다. m은 쿼리 수입니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
위 내용은 하위 트리 제거 쿼리 후 이진 트리의 높이의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!