하위 트리 제거 쿼리 후 이진 트리의 높이

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. 1부터 n까지 각 노드에 대한 답을 미리 계산하고 각 쿼리에 O(1)로 답해 보세요.
2. 각 하위 트리의 높이를 계산한 후 단일 트리 순회에서 답변을 미리 계산할 수 있습니다.

해결책:

이 솔루션은 2단계 접근 방식을 사용합니다.

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입니다.

쿼리 후 결과 배열:

• 쿼리 4의 경우 결과는 [2]입니다.

최종 출력

제공된 입력의 결과는 다음과 같습니다.

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

이 구조화된 접근 방식을 통해 필요한 높이를 효율적으로 계산하고 초기 전처리 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다. 전체 복잡도는 O(n·m)입니다. 여기서 n은 트리의 노드 수이고 입니다. m은 쿼리 수입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 하위 트리 제거 쿼리 후 이진 트리의 높이의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!