[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Construct Binary Tree from Preorder and Inorder Traversal - LeetCode>

1. 문제 (전위, 중위 순회 결과로 이진 트리 구축)

트리의 전위, 중위 순회로 결과를 입력값으로 받아 이진 트리를 구축하라.

2. 풀이

전위의 첫번 째 값은 부모 노드이며 중위 순회 결과를 left와 right로 나누는 역할을 한다.

• 전위 순회의 값을 순차적으로 빼면서 중위 순회를 left와 right로 나눈다.

3. 코드

# Definition for a binary tree node.
# 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]) -> 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

• 결과 :

방식	Status	Runtime	Memory	Language
순회	[Accepted]	132 ms	52.6 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋