[Leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

1) 코드

from collections import deque 

# 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 = deque(preorder)

        def dfs(inorder): 
            if len(inorder) == 0:
                return 

            num = preorder.popleft() 
            pos = inorder.index(num)

            root = TreeNode(num)

            root.left = dfs(inorder[:pos])
            root.right = dfs(inorder[pos+1:])

            return root 

        return dfs(inorder)

2) 해설

• Preorder에서 값을 왼쪽부터 하나씩 꺼낸 다음에,
  해당 값의 위치를 찾고, 그 위치 기준으로 왼쪽과 오른쪽으로
  계속해서 재귀적으로 이진 트리를 탐색한다.