105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

 

https://youtu.be/ihj4IQGZ2zc?si=xp7MO4VGo3NIKjnW

 

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 문제 접근법:
        # 1. Preorder 배열의 첫 번째 값은 항상 현재 서브트리의 루트 노드 값입니다.
        # 1. The first value in the preorder array is always the root node of the current subtree.
        # 2. Inorder 배열에서 루트 값의 인덱스를 찾아:
        #    - 루트 값 왼쪽의 값들은 왼쪽 서브트리에 속합니다.
        #    - 루트 값 오른쪽의 값들은 오른쪽 서브트리에 속합니다.
        # 2. Find the index of the root value in the inorder array:
        #    - Values to the left of the root belong to the left subtree.
        #    - Values to the right of the root belong to the right subtree.
        # 3. Preorder 배열은 다음과 같이 구성됩니다:
        #    - 첫 번째 값 이후, 왼쪽 서브트리에 해당하는 값들.
        #    - 이어서 오른쪽 서브트리에 해당하는 값들.
        # 3. The preorder array is structured as follows:
        #    - After the first value, the next values belong to the left subtree.
        #    - Then, the subsequent values belong to the right subtree.
        # 4. 이 과정을 재귀적으로 반복하여 트리를 구성합니다.
        # 4. Repeat this process recursively to construct the tree.

        # Base case: 만약 preorder와 inorder 배열이 모두 비었다면, 트리를 만들 수 없으므로 None을 반환
        # Base case: If both preorder and inorder arrays are empty, return None as the tree cannot be constructed.
        if not preorder and not inorder: 
            return None

        # Preorder의 첫 번째 값은 현재 서브트리의 루트 노드 값
        # The first value in the preorder array is the root node of the current subtree.
        root = TreeNode(preorder[0])
        
        # Inorder에서 현재 루트 값의 인덱스를 찾음
        # Find the index of the root value in the inorder array.
        # 이 인덱스를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리를 나타냄
        # Use this index to determine the left and right subtrees.
        mid = inorder.index(preorder[0]) 

        # 왼쪽 서브트리 구성
        # Construct the left subtree.
        # preorder[1:mid+1]: preorder에서 왼쪽 서브트리에 해당하는 값들 (루트 이후 mid개)
        # preorder[1:mid+1]: Values in preorder that belong to the left subtree (first mid elements after root).
        # inorder[:mid]: inorder에서 왼쪽 서브트리에 해당하는 값들 (mid까지)
        # inorder[:mid]: Values in inorder that belong to the left subtree (up to mid index).
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        
        # 오른쪽 서브트리 구성
        # Construct the right subtree.
        # preorder[mid+1:]: preorder에서 오른쪽 서브트리에 해당하는 값들
        # preorder[mid+1:]: Values in preorder that belong to the right subtree.
        # inorder[mid+1:]: inorder에서 오른쪽 서브트리에 해당하는 값들
        # inorder[mid+1:]: Values in inorder that belong to the right subtree.
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        
        # 현재 서브트리의 루트 노드를 반환
        # Return the root node of the current subtree.
        return root

 

# preorder: 현재->왼->오

# inoderder: 왼->현->오

# 그래서, preorder 에서 현재 값 을 inoder 에서 index 찾아서 그 왼쪽이 left,

# 현재값,

# preoder에서 left 의 개수 만큼.. 넘어가면.. right임

 

# 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: 현재->왼->오
        # inoderder: 왼->현->오
        # 그래서, preorder 에서 현재 값 을 inoder 에서 index 찾아서 그 왼쪽이 left, 
        # 현재값,
        # preoder에서 left 의 개수 만큼.. 넘어가면.. right임

        if not preorder and not inorder: # 둘다 비었으면
            return None

        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0]) 

        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root

 

 

최종 코드

# 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: 자신,왼,오 | inorder: 왼,자신,오
        if not preorder and not inorder: # 둘다 null 이면
            return None

        """
        # preorder의 첫번째가 root임
        """
        root_val = preorder[0]
        root = TreeNode(root_val)

        """
        # inorder에서 자신(root) 인덱스 전 까지가 left
        # => inorder에서 자신(root) 인덱스: left 개수
        """
        nums_left = inorder.index(root_val) 

        root.left = self.buildTree(preorder[1:nums_left+1], inorder[:nums_left])

        # 둘다 right 는 같음, 단 자기자신 제외
        root.right = self.buildTree(preorder[nums_left+1:], inorder[nums_left+1:])

        return root