[파이썬 알고리즘 인터뷰][트리] 전위,중위 순회 결과로 이진 트리 구축

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

전위순회와 중위순회 정보로 이진 트리 만들기

 

책에서 구현된 코드

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

 

기억해야할 기법

• 중첩 함수를 사용하지 않는 재귀 방법
  
  • 중첩 함수 없이도 재귀를 사용할 수 있으면 더 깔끔한 코드가 되는 듯

 

내가 구현한 코드

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        q = deque(preorder[:])
        def dfs(nodes: List[int]):
            if len(nodes) == 0:
                return None
            idx = nodes.index(q.popleft())
            root = TreeNode(nodes[idx])
            root.left = dfs(nodes[:idx])
            root.right = dfs(nodes[idx+1:])
            return root

        return dfs(inorder)

• 책에 구현된 코드가 list에서 pop(0)를 사용해서 deque로 구현한 내 코드가 약간 더 빠름