[1스4코2파] # 213 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (213차)
[4코1파] 2023.01.13~ (205일차)
[1스4코1파] 2023.04.12~ (116일차)
[1스4코2파] 2023.05.03 ~ (94일차)

Today :

2023.08.05 [213일차]
Tree
105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

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

문제 설명

binary tree의 preorder 전위 순회 순서가 담긴 배열과 inorder 중위 순회 순서가 담긴 배열이 주어진다고 했을 때, 해당 tree structure를 return 하는 것

문제 풀이 방법

preorder는 왼쪽노드-루트-오른쪽노드 순서
inorder는 루트-왼쪽노드-오른쪽노드 순서이므로
이를 이용해서 본래의 tree structure를 return 한다.
preorder에서 root를 찾고 inorder에서 preorder의 원소를 기준으로 왼쪽, 오른쪽 노드를 찾으면 됨

내 코드

# 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]:

        if not preorder or 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

증빙

여담

톱밥