Subtree of Another Tree

Q: Subtree of Another Tree의 시간 복잡도는 얼마인가요?

모든 노드에서 비교하면 최악의 경우 비용은 O(n·m) 이며, 여기서 n 과 m 은 두 트리의 크기입니다. subRoot 의 높이와 같은 높이를 가진 노드에서만 비교하면 O(n + m) 이 됩니다. 이렇게 하면 root 의 각 노드를 최대 한 번만 순회하기 때문입니다.

Q: 문자열 매칭으로 다른 트리의 서브트리인지 판별할 수 있을까요?

네. 각 트리를 전위 순회 순서로 적고, 비어 있는 자식마다 # 을 쓰며 각 값 앞에 구분자를 넣으세요: ,2,1,#,#,3,#,# . subRoot 의 문자열이 root 의 문자열 안에 나타날 때에만 subRoot 는 부분 트리이며, KMP는 이를 O(n + m) 에 찾습니다. 표시자가 없으면 서로 다른 모양의 트리가 같은 문자열을 만들고, 구분자가 없으면 12 에 2 가 포함됩니다.

Q: subRoot와 일치하지만 자식 노드가 더 있는 노드도 포함되나요?

아니요. 서브트리는 노드와 그 모든 자손을 함께 포함하므로, 일치하는 노드 아래의 모든 노드도 subRoot 에 있어야 합니다. 두 번째 예에서는 3 아래에 추가된 0 때문에 답은 false 입니다.

쉬움트리 순회 재귀

+10

두 개의 이진 트리 root와 subRoot가 주어집니다. 각 트리는 레벨 순서대로 배열에 저장되어 있습니다. 루트는 인덱스 0에 있고, 인덱스 i의 자식은 2*i+1(왼쪽)과 2*i+2(오른쪽)에 있으며, 빈 위치는 -1로 표시됩니다. 배열은 끝에 여분의 -1 항목이 포함된 채 끝날 수도 있습니다.

root의 어떤 노드와 그 노드의 모든 자손이 subRoot와 모양과 값이 정확히 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. root 전체도 해당됩니다.

함수

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: 검색할 트리. 레벨 순서로 표시하며, 빈 자리는 -1로 나타냅니다.
subRootinteger-array: 찾아야 할 트리, 동일한 형식으로
반환값boolean: true: subRoot가 모든 자손을 포함하는 노드로 루트에 나타나는 경우, 그렇지 않으면 false

제약 조건

1 ≤ root.length ≤ 32767 그리고 1 ≤ subRoot.length ≤ 32767
각 항목은 -1이거나 0부터 10⁴까지의 값입니다.
root[0]과 subRoot[0]은 절대 -1이 아니므로 두 트리 모두 노드가 하나 이상 있습니다.
어느 배열이든 마지막 노드 뒤에 추가 -1 항목이 올 수 있습니다.
빈 자리의 두 자식도 모두 비어 있으며, 각 트리의 깊이는 최대 14입니다.
값은 반복될 수 있습니다.

예제

입력: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
출력: true
설명: 인덱스 1의 노드 2에는 자식 1과 3이 있으며, 둘 다 리프입니다. 이것이 바로 subRoot입니다.

입력: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
출력: false
설명: 노드 2 아래의 3에는 이제 자식 0이 있습니다. 서브트리에는 모든 자손이 포함되므로, 노드 2의 서브트리는 subRoot의 서브트리에 있는 세 개보다 많은 네 개의 노드를 포함하며, 다른 어떤 노드에도 2는 없습니다.

입력: root = [5, 5, 7]subRoot = [5]
출력: true
설명: 루트 5에는 자식이 두 개 있으므로 단일 노드 5와 일치하지 않습니다. 인덱스 1에 있는 5는 리프이며 일치합니다.

후속 질문

값과 자식들의 지문을 사용해 모든 하위 트리의 지문을 만들면, subRoot와의 비교 비용을 O(1)로 만들 수 있을까요? 서로 다른 두 하위 트리의 지문이 충돌하면 어떻게 해야 할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이 문제는 두 부분으로 나뉩니다. 두 트리가 동일한지 판단하는 것과, root의 어느 위치에서 그 검사를 실행할지 선택하는 것입니다. 높이가 subRoot의 높이와 같은 노드만 일치할 수 있으며, 같은 높이의 노드들은 서로 겹치지 않으므로 해당 노드만 검사하면 root의 각 노드를 최대 한 번씩 방문하게 됩니다.

각 노드에서 비교

핵심 아이디어

i 위치는 i가 배열 안에 있고 해당 위치의 값이 -1이 아닐 때 유효합니다. 두 트리는 둘 다 비어 있거나, 루트에 같은 값이 있고 왼쪽 하위 트리와 오른쪽 하위 트리가 각각 동일할 때 동일합니다. same(i, j)는 i에서 시작하는 root와 j에서 시작하는 subRoot를 동시에 탐색합니다. subRoot가 root에 나타난다면 그 루트는 어떤 노드에 위치하므로, 유효한 모든 i에서 same(i, 0)을 시도합니다.

거의 일치하는 경우 실패하기 전에 최대 m단계를 탐색할 수 있으며, 이는 n개의 노드 각각에 대해 수행됩니다. 따라서 시간 복잡도는 O(n·m)입니다. 여기서는 깊이 제한으로 탐색 횟수가 제한됩니다. 한 노드는 해당 노드에서 시작하거나 그 위에서 시작하는 검사에서만 탐색되므로, 최대 14번 탐색됩니다.

알고리즘

same(i, j)를 작성하세요. root의 위치 i와 subRoot의 위치 j가 모두 비어 있으면 true를 반환하고, 둘 중 정확히 하나만 비어 있으면 false를 반환하세요.
두 값이 다르면 false를 반환하세요. 그렇지 않으면 same(2*i+1, 2*j+1)과 same(2*i+2, 2*j+2)를 반환하세요.
root의 실제 인덱스 i 중 same(i, 0)이 성립하는 것이 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

높이가 일치하는 경우에만 비교하세요

핵심 아이디어

동일한 트리는 아래쪽으로 이어지는 가장 긴 경로의 노드 수로 계산한 높이가 같습니다. 따라서 높이가 subRoot의 높이와 같은 root의 노드만 확인하면 됩니다. 첫 번째 예시에서 subRoot의 높이는 2이고, root에서는 2와 8만 해당합니다.

노드는 아래에 있는 모든 노드보다 높으므로 높이가 같은 두 노드가 서로의 하위 트리에 속할 수는 없습니다. 각 확인은 시작 노드의 하위 트리만 탐색하므로, 모든 확인을 합쳐도 root의 각 노드는 최대 한 번만 탐색합니다.

자식은 부모보다 큰 인덱스에 있으므로, 마지막 인덱스부터 순회하면 부모보다 먼저 두 자식에 도달합니다. 높이를 구하는 두 번의 순회와 확인 작업은 O(n + m) 시간이 걸립니다.

알고리즘

각 트리에 대해 마지막 인덱스부터 0까지 역순으로 순회하며 높이 배열을 채웁니다. 빈 위치에는 0을 넣고, 실제 노드에는 두 자식의 높이 중 더 큰 값에 1을 더한 값을 넣습니다.
높이가 subRoot의 인덱스 0의 높이와 같은 root의 모든 인덱스 i에 대해 same(i, 0)을 실행하고, 참이면 true를 반환합니다.
false를 반환합니다.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

함정과 경계 사례

두 번째 예시처럼 부분 일치를 허용하는 경우입니다. root에 subRoot의 빈 자리에 해당하는 노드가 있으면 same은 실패해야 합니다.
올바른 값을 가진 첫 번째 노드에서 멈추는 경우입니다. 세 번째 예시에서는 루트의 5는 일치하지 않고 그 아래의 리프 5는 일치합니다.
두 배열의 슬라이스를 비교하는 경우입니다. 서브트리의 노드는 여러 레벨에 걸쳐 퍼져 있으며, 두 배열 중 하나는 뒤에 추가 -1 항목이 있을 수 있습니다. 끝을 지난 인덱스는 -1과 마찬가지로 빈 자리입니다.
Lua와 R에서는 2*i+1 계산을 위해 노드 인덱스를 0부터 시작하도록 유지하고 root[i + 1]을 읽습니다.

자주 묻는 질문3

Subtree of Another Tree의 시간 복잡도는 얼마인가요?

모든 노드에서 비교하면 최악의 경우 비용은 O(n·m)이며, 여기서 n과 m은 두 트리의 크기입니다. subRoot의 높이와 같은 높이를 가진 노드에서만 비교하면 O(n + m)이 됩니다. 이렇게 하면 root의 각 노드를 최대 한 번만 순회하기 때문입니다.

문자열 매칭으로 다른 트리의 서브트리인지 판별할 수 있을까요?

네. 각 트리를 전위 순회 순서로 적고, 비어 있는 자식마다 #을 쓰며 각 값 앞에 구분자를 넣으세요: ,2,1,#,#,3,#,#. subRoot의 문자열이 root의 문자열 안에 나타날 때에만 subRoot는 부분 트리이며, KMP는 이를 O(n + m)에 찾습니다. 표시자가 없으면 서로 다른 모양의 트리가 같은 문자열을 만들고, 구분자가 없으면 12에 2가 포함됩니다.

subRoot와 일치하지만 자식 노드가 더 있는 노드도 포함되나요?

아니요. 서브트리는 노드와 그 모든 자손을 함께 포함하므로, 일치하는 노드 아래의 모든 노드도 subRoot에 있어야 합니다. 두 번째 예에서는 3 아래에 추가된 0 때문에 답은 false입니다.

def isSubtree(root, subRoot):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

예상 출력

true