[LEET CODE] 105. Construct Binary Tree from Preorder and Inorder Traversal

# Problem

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.     Constraints: 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.

전위, 중위 순회의 결과를 받아 이진 트리 구축하기

 

# My Answer

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder)==0:
            return
        node = TreeNode(preorder[0])
        l = inorder[:inorder.index(node.val)]
        node.left = self.buildTree(preorder[1:len(l)+1],l)
        node.right = self.buildTree(preorder[len(l)+1:],inorder[inorder.index(node.val)+1:])
        return node

preorder는 현재 노드 값이 먼저 나오므로 인덱스 0의 원소가 현재 노드이고 

[N, (left), (right)] 순서

inorder는 현재 노드가 중간에 나오므로 preorder에서 구한 현재 노드의 왼쪽에 있는 값들이 왼쪽 트리 구성, 

오른쪽에 있는 값들이 오른쪽 트리를 구성한다.

[(left), N, (right)] 순서

inorder에서 현재 노드를 중심으로 left와 right를 구분해 재귀함수 호출

 

# Solution 1 - 전위 순회의 결과로 중위 순회 분할 정복

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> 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

preorder에서 하나씩 pop()해서 그 값을 기준으로 inorder를 나눠서 재귀 호출

preorder에서 하나씩 pop()하므로 preorder 그대로 재귀함수 호출