Construct Binary Tree from Preorder and Inorder Traversal

Q: 이진 트리를 재구성하려면 왜 전위 순회와 중위 순회가 모두 필요한가요?

전위 순회만으로는 트리의 구조를 확정할 수 없습니다. 전위 순회 결과 [1, 2] 는 2 가 1 의 왼쪽 자식인 트리와 오른쪽 자식인 트리 모두에 해당할 수 있습니다. 중위 순회 결과를 함께 보면 확정됩니다. [2, 1] 은 2 가 왼쪽에 있음을, [1, 2] 는 오른쪽에 있음을 나타냅니다. 값이 서로 다르면 이 두 순회 결과의 조합으로 트리가 하나로 정해집니다.

Q: 전위 순회와 중위 순회로 이진 트리를 구성하는 시간 복잡도는 얼마인가요?

값에서 중위 순회 위치로의 맵을 사용하면 시간은 O(n) 이고 추가 공간은 O(n) 입니다. 맵이 없으면 각 중위 순회 범위에서 루트를 검색하는 데 O(n·h) 가 걸리며, 이는 경로 형태의 트리에서 O(n²) 가 됩니다.

Q: 전위 순회와 후위 순회로 이진 트리를 재구성할 수 있나요?

일반적으로는 그렇지 않습니다. 전위 순회 [1, 2] 와 후위 순회 [2, 1] 는 왼쪽 자식과 오른쪽 자식 모두에 해당할 수 있습니다. 두 순회 모두 루트를 하위 트리 사이에 배치하지 않기 때문입니다. 모든 노드가 자식이 0개이거나 2개인 포화 이진 트리에서만 이 순회 쌍으로 충분합니다.

보통트리 순회 해싱 재귀

+10

같은 이진 트리의 서로 다른 값을 나열하는 두 배열 preorder와 inorder가 주어집니다. 전위 순회는 노드, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문합니다. 중위 순회는 왼쪽 서브트리, 노드, 오른쪽 서브트리 순으로 방문합니다.

트리를 재구성하고 레벨 순서대로 배열에 담아 반환하세요. 루트는 인덱스 0에, 인덱스 i의 자식은 2i+1(왼쪽)과 2i+2(오른쪽)에 배치하고, 비어 있는 모든 위치에는 -1을 넣습니다. 배열은 마지막 노드에서 끝나며, 뒤에 -1을 붙이지 않습니다.

함수

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: 전위 순회의 값: 노드, 왼쪽 하위 트리, 오른쪽 하위 트리
inorderinteger-array: 중위 순회의 값: 왼쪽 하위 트리, 노드, 오른쪽 하위 트리
반환값integer-array: 레벨 순서로 나타낸 트리이며, 빈 위치는 -1로 표시하고 끝에는 -1을 붙이지 않음

제약 조건

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴이고, 모든 값은 서로 다릅니다.
inorder에는 동일한 값이 들어 있으며, 두 배열은 동일한 이진 트리를 나타냅니다.
트리의 깊이는 최대 14이므로, 답에 있는 모든 인덱스는 2¹⁴-1 = 16383보다 작습니다.

예제

입력: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
출력: [7, 3, 4, 0, 9, -1, 6]
설명: 전위 순회는 루트인 7에서 시작합니다. 이 값은 inorder에서 3번째 위치에 있으므로, 0, 3, 9는 왼쪽으로 가고 4, 6은 오른쪽으로 갑니다. 4에는 오른쪽 자식인 6만 있으므로, 인덱스 5는 -1로 유지됩니다.

입력: preorder = [1, 2, 3]inorder = [2, 3, 1]
출력: [1, 2, -1, -1, 3]
설명: 루트 1은 inorder에서 마지막에 나오므로 인덱스 2는 -1입니다. 2, 3 중에서 preorder에는 2가 먼저 나오고 inorder에서는 그 뒤에 3이 나오므로, 3은 인덱스 4에 있는 2의 오른쪽 자식입니다.

후속 질문

명시적 스택을 사용해 preorder를 한 번 순회하면서 재귀 없이 트리를 다시 구성할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

전위 순회는 모든 하위 트리의 루트를 알려 줍니다. 즉, 해당 구간의 첫 번째 값입니다. 중위 순회는 분할 지점을 알려 줍니다. 루트 앞의 값은 왼쪽으로, 뒤의 값은 오른쪽으로 갑니다. 두 절반에 재귀를 적용하면 트리를 재구성할 수 있으며, 값에서 중위 순회 위치로 연결하는 맵을 사용하면 각 루트를 한 단계만에 찾을 수 있습니다.

루트를 찾으며 재귀적으로 분할하기

핵심 아이디어

전위 순회에서는 왼쪽 서브트리가 루트 뒤에 오며, 값마다 하나씩 총 m-lo개의 항목을 차지합니다. 여기서 m은 루트의 중위 순회 위치입니다. 오른쪽 서브트리는 그 뒤에 오므로, 그 루트는 pre+1+(m-lo)에 위치합니다. 첫 번째 예시에서 왼쪽 부분 0, 3, 9에는 값이 세 개 있으므로, 오른쪽 서브트리는 전위 순회 인덱스 4, 즉 값 4에서 시작합니다.

깊이가 최대 14이면 모든 출력 인덱스가 2^14-1보다 작습니다. 그만큼의 셀을 -1로 채우고, 각 값을 해당 인덱스에 기록한 다음, 마지막에 뒤쪽의 -1 항목을 잘라 냅니다.

각 중위 순회 범위에서 루트를 찾는 데는 O(n·h)의 비용이 듭니다. 같은 레벨의 범위는 겹치지 않으므로, 한 레벨에서 최대 n개의 항목을 탐색합니다. 여기서는 최대 14 × 3000 = 42000번의 단계입니다. 깊이 제한이 없다면 경로 모양의 트리에서 비용이 O(n²)이 됩니다.

알고리즘

모든 항목이 -1인 2^14-1개의 항목으로 out을 만듭니다.
build(pre, lo, hi, h)를 작성합니다. lo > hi이면 반환합니다. 그렇지 않으면 preorder[pre]를 out[h]에 씁니다.
inorder에서 lo부터 루트의 위치 m을 찾습니다. 왼쪽 하위 트리에는 m-lo개의 값이 있습니다.
build(pre+1, lo, m-1, 2*h+1)과 build(pre+1+(m-lo), m+1, hi, 2*h+2)를 호출합니다.
build(0, 0, n-1, 0)을 호출한 다음, 끝에 있는 -1 항목을 제거하고 나머지를 반환합니다.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

위치 맵을 사용하여 재귀적으로 분할

핵심 아이디어

값은 서로 다르므로 각 값은 inorder에서 정확히 한 위치를 차지합니다. 재귀를 시작하기 전에 값에서 위치로 매핑하는 맵에 그 위치를 기록하면, 루트를 찾을 때마다 한 단계만 거치면 됩니다.

맵을 만드는 데 O(n)이 걸리고, 각 값은 일정한 작업으로 한 번씩 배치되므로 총 시간은 O(n)입니다. 맵은 O(n)의 공간을 차지하고, 재귀는 각 레벨마다 프레임 하나를 사용합니다. C와 R에서는 값이 최대 10^4이므로, 10^4+1개의 항목이 있는 일반 배열을 맵으로 사용할 수 있습니다.

알고리즘

inorder의 각 값에서 해당 위치로 매핑되는 맵을 만듭니다.
모두 -1인 2^14-1개의 항목으로 out을 만듭니다.
build(pre, lo, hi, h)에서 lo > hi이면 반환합니다. 그렇지 않으면 preorder[pre]를 out[h]에 쓰고, 맵에서 해당 값의 위치 m을 찾습니다.
build(pre+1, lo, m-1, 2*h+1)과 build(pre+1+(m-lo), m+1, hi, 2*h+2)를 재귀적으로 호출합니다.
build(0, 0, n-1, 0)을 호출한 다음, 뒤에 이어지는 -1 항목을 제거하고 나머지를 반환합니다.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

함정과 경계 사례

오른쪽 서브트리를 pre+1+(m-lo) 대신 pre+1+m에서 시작하는 경우입니다. 최상위 호출처럼 lo가 0일 때는 작동하지만, 범위가 나중에 시작하면 문제가 발생합니다.
간격을 없애는 경우입니다. 자식 노드가 없어도 해당 슬롯은 유지되므로, 두 번째 예제의 답은 [1, 2, -1, -1, 3]이지 [1, 2, 3]이 아닙니다.
뒤에 붙는 -1 항목을 남겨 두는 경우입니다. 2^14-1개의 셀을 모두 반환하면 첫 번째 예제에는 -1 항목이 16376개 더 들어갑니다.
호출할 때마다 두 배열의 슬라이스를 모두 복사하면 레벨마다 O(n)이 추가됩니다. 인덱스 범위를 전달하세요.
Lua와 R에서는 배열이 1부터 시작합니다. 계산에는 위치를 0부터 시작하는 것으로 유지하고 preorder[pre + 1]과 out[h + 1]을 읽으세요.

자주 묻는 질문3

이진 트리를 재구성하려면 왜 전위 순회와 중위 순회가 모두 필요한가요?

전위 순회만으로는 트리의 구조를 확정할 수 없습니다. 전위 순회 결과 [1, 2]는 2가 1의 왼쪽 자식인 트리와 오른쪽 자식인 트리 모두에 해당할 수 있습니다. 중위 순회 결과를 함께 보면 확정됩니다. [2, 1]은 2가 왼쪽에 있음을, [1, 2]는 오른쪽에 있음을 나타냅니다. 값이 서로 다르면 이 두 순회 결과의 조합으로 트리가 하나로 정해집니다.

전위 순회와 중위 순회로 이진 트리를 구성하는 시간 복잡도는 얼마인가요?

값에서 중위 순회 위치로의 맵을 사용하면 시간은 O(n)이고 추가 공간은 O(n)입니다. 맵이 없으면 각 중위 순회 범위에서 루트를 검색하는 데 O(n·h)가 걸리며, 이는 경로 형태의 트리에서 O(n²)가 됩니다.

전위 순회와 후위 순회로 이진 트리를 재구성할 수 있나요?

일반적으로는 그렇지 않습니다. 전위 순회 [1, 2]와 후위 순회 [2, 1]는 왼쪽 자식과 오른쪽 자식 모두에 해당할 수 있습니다. 두 순회 모두 루트를 하위 트리 사이에 배치하지 않기 때문입니다. 모든 노드가 자식이 0개이거나 2개인 포화 이진 트리에서만 이 순회 쌍으로 충분합니다.

def buildTree(preorder, inorder):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자들

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

예상 출력

[7, 3, 4, 0, 9, -1, 6]