[코테] 리트코드 트리 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/description/

문제 설명

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

제한 사항

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

입출력 예 #1

1. Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
2. Output : [3,9,20,null,null,15,7]

입출력 예 #2

1. Input : preorder = [-1], inorder = [-1]
2. Output : [-1]

문제 풀이

전위 구조는 첫 번째 결과는 중위 순회 결과의 왼쪽과 오른쪽을 나누는 역할

따라서 분할 정복을 통해 문제를 풀이한다.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if inorder:
            # 전위 순회 결과는 중위 순회 분할 인덱스
            index = inorder.index(preorder.pop(0))

            # 중위 순회 결과 분할 정복
            node = TreeNode(inorder[index])
            node.left = self.buildTree(preorder, inorder[0:index])
            node.right = self.buildTree(preorder, inorder[index + 1:])

            return node