Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

문제

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.

특정 트리의 preorder 순회와 inorder 순회의 결과를 담은 두 배열이 주어진다. 이 둘에 다 해당되는 특정한 트리를 리턴하시오.

예시

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

제한

• $1 <= preorder.length <= 3000$
• $inorder.length == preorder.length$
• $-3000 <= preorder[i], inorder[i] <= 3000$
• 노드의 값은 동일한 값을 하나도 가지고 있지 않다.
• 정답으로 나올수 있는 트리는 유일하다.

풀이

위 예시로 풀이를 해 볼수 있다.

자세하게...

• Preorder의 경우 Center -> Left -> Right 의 순서로 순회 한다.
• 즉 Preorder의 결과를 왼쪽에서 오른쪽 순서로 읽으면 전체 트리의 맨 위 head인 3, 왼쪽 subtree의 맨 위 head인 9 ... 가 된다.
• 이를 통해 Inorder에서의 정확한 Center위치를 알수 있다.
• Inorder에서 위에서 얻은 결과를 통해 왼쪽 노드, 부모값, 오른쪽 노드를 정할수 있으며 이를 재귀적으로 실행해 트리를 구한다.

코드

• 노드에 들어갈 리스트의 길이가 0인 경우는 NULL인 경우이기에, 이를 제외해야 한다.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        self.current_index = 0
        self.tree = None
        
        def create_tree(tree_node: TreeNode, inorder_list: List[int]):
            if len(inorder_list) == 0:
                return
            tree_node = TreeNode(preorder[self.current_index], None, None)
            self.current_index += 1
            tree_node.left = create_tree(tree_node.left, inorder_list[:inorder_list.index(tree_node.val)])
            tree_node.right = create_tree(tree_node.right, inorder_list[inorder_list.index(tree_node.val) + 1:])
            return tree_node
            
        self.tree = create_tree(self.tree, inorder)
        return self.tree