[Pythonn] LeetCode - 105. Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 105번 Construct Binary Tree from Preorder and Inorder Traversal 문제는 전위 순회 배열과 중위 순회 배열을 통해 이진 트리를 구성하는 문제다. 난이도는 중(Medium)이며 분할 정복을 통해 해결할 수 있다.

 

리트코드 105번 Construct Binary Tree from Preorder and Inorder Traversal 문제 정보

알고리즘 분류

• 트리 순회

난이도

• Medium

 

문제 요약

• 105번 문제는 전위 순회와 중위 순회 정보를 가지고 이진 트리를 구성하는 문제이다.
• input: preorder (전위 순회 리스트), inorder (중위 순회 리스트)
• output: 트리의 루트 노드

문제 풀이 방법

풀이

• 전위, 중위, 후위 순회 중 2가지만 있어도 트리를 다시 복구할 수 있다. 이 문제에서는 전위, 중위 순회 값이 주어졌다.
• preorder의 가장 첫번째 값은 트리의 루트가 된다. 그리고 루트의 값을 inorder 배열에서 찾으면, 찾은 값의 왼쪽 배열은 좌측 서브트리이며 오른쪽 배열은 우측 서브트리임을 알 수 있다.
• 그렇게 각 서브트리마다 재귀적으로 자식 노드를 연결해가며 풀 수 있는 문제이다.

 

코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # preorder 배열을 따라가는 인덱스. 노드를 트리에 추가할 때마다 하나씩 증가함.
        self.pre_idx = 0
        
        # inorder 배열에서 서브트리의 위치 left, right 정보를 받아서
        # 서브트리의 root 노드를 만들고 자식들을 연결해서 반환해주는 함수
        def find_children(left, right):
            # 트리의 루트 노드 생성. 노드를 추가했으므로 pre_idx를 1 증가시킴
            root_val = preorder[self.pre_idx]
            root = TreeNode(root_val, None, None)
            self.pre_idx += 1
            
            # 트리의 루트 노드의 값을 통해서 왼쪽/오른쪽 서브트리가 있는지 확인
            # 서브 트리가 있으면 해당 서브트리의 루트 = 현재 루트의 자식을 구해서 설정해줌
            inorder_idx = inorder.index(root_val)
            if left < inorder_idx:
                root.left = find_children(left, inorder_idx-1)
            if inorder_idx < right:
                root.right = find_children(inorder_idx+1, right)
            
            # 트리의 루트 노드 반환
            return root
                
    
        return find_children(0, len(preorder)-1)