[LeetCode 해석 및 풀이] 105. Construct Binary Tree from Preorder and Inorder Traversal(선위, 중위 순회에서 이진 트리 구성)

LeetCode 문제 해석 및 풀이 방법

문제 105. Construct Binary Tree from Preorder and Inorder Traversal(선위, 중위 순회에서 이진 트리 구성)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

 

한글

 이진 트리의 선위 순회인 preorder 와 동일한 트리의 중위 순회인 inorder, 두 개의 정수 배열이 주어질 때, 원래 이진 트리를 구성하고 반환합니다.

 

제한조건

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

 

입출력 예

입력	출력
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]	[3,9,20,null,null,15,7]
preorder = [-1], inorder = [-1]	[-1]

 

해답 및 해설

파이썬 (Python)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def buildTreeHelper(preorder, inorder):
            if not (preorder and inorder):
                return None
            
            root_val = preorder[0]
            root = TreeNode(root_val)
            mid = inorder.index(root_val)
            root.left = buildTreeHelper(preorder[1:mid+1], inorder[:mid])
            root.right = buildTreeHelper(preorder[mid+1:], inorder[mid+1:])

            return root
        return buildTreeHelper(preorder, inorder)

 선위 순회란 루트 -> 왼쪽 -> 오른쪽 순으로 순회하는 것이고, 중위 순회란 왼쪽 -> 루트 -> 오른쪽 순으로 순회하는 것이다. 이때 선위 순위의 맨 앞 원소는 루트 노드가 되고, 이를 중위순위 리스트에서 위치를 찾으면 왼쪽 하위 트리의 노드가 들어있는 범위가 어디까지인지 알 수 있다. 그럼 각각 왼쪽, 오른쪽 하위 트리에 대해서 재귀로 구해주면 된다.

 

해당 풀이법 외에 해쉬 맵으로 시간을 단축한 풀이와 다른 방식으로 메모리를 최적화한 풀이가 있던데 그 풀이는 나중에 한번 확인해보자.