105. Construct Binary Tree from Preorder and Inorder Traversal - python3

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

일단 다 insert 하고 정렬한다는 저질스런 방식만 생각나서 답을 봤읍니다..^^

Recursive

Solution 1: Runtime: 200 ms - 27.36% / Memory Usage: 88.3 MB - 22.90%

# 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]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        root = TreeNode(preorder[0])
        i = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:1+i], inorder[:i])
        root.right = self.buildTree(preorder[1+i:], inorder[i+1:])
        
        return root

이해하기 쉬워보이는 걸로 가져옴

1. preorder[0] 값을 넣어서 트리노드를 만들어줌

2. inorder 에서의 index 값을 알아내서 (root 를 잡아줌)

3. preorder: root 가 맨 앞에 위치 / inorder: root 가 가운데 위치
   를 기준으로 슬라이싱해서 왼쪽, 오른쪽에 넣어준다.

이거 뭔가 무조건 외우는게 좋을듯한 늬낌