54. Construct Binary Tree from Preorder and Inorder Traversal

🎯 leetcode - 105. Construct Binary Tree from Preorder and Inorder Traversal

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 54번 문제
- 전위, 중위 값으로 이진트리 구현하기

📌 날짜

2020.02.24

📌 시도 횟수

3 try

💡 Code

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not inorder:
            return None

        # preorder의 맨 앞의 원소를 pop 한게 현재 범위에서 inorder의 루트임
        curr = TreeNode(preorder.pop(0))
        
        curr.left = self.buildTree(preorder, inorder[: inorder.index(curr.val)])
        curr.right = self.buildTree(preorder, inorder[inorder.index(curr.val) + 1 :])

        return curr

💡 문제 해결 방법]

• 예시로 이러한 이진 트리가 있다고 가정하자.
  
• 전위, 중위 순회로 위의 이진트리를 구축하는 방법은 다음과 같다.
  

- 추가 설명
1. 전위 순회의 첫번째 값은 정확히 중회 순회 결과를 왼/오른쪽으로 분할시킨다. 
2. 더이상 분할할 중회순회가 없을 때까지 1을 반복한다.
3. 재귀 호출 후 return node로 아래부터 트리를 완성한다.

💡 새롭게 알게 된 점

- 전위와 중위 사이에 어떠한 규칙이 있는지 알게 되었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 전위, 중위 사이의 관계를 처음에는 파악하지 못했다.
- 이 관계에 대한 설명을 책에서 읽은 후에야 구현할 수 있었다.

---