[파이썬 알고리즘] 14장 - pre/in-order traversal (leetcode 105) - 재귀

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

<문제>

Given preorder and inorder traversal of a tree, construct the binary tree.

 

<예시>

For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

---

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:
            value = preorder.pop(0)
            index = inorder.index(value)
            
            node = TreeNode(value)
            node.left = self.buildTree(preorder, inorder[:index])
            node.right = self.buildTree(preorder, inorder[index+1:])
            return node

 

자료구조 시간에 "in-order traversal와 pre-order traversal가 주어지면 binary tree는 유일하게 결정된다."

라는 내용을 배웠었기 때문에 문제 풀이 방법은 쉽게 떠올랐다.

 

하지만 코드 작성에서 어려움을 겪었다.

예제를 보면 이해가 되는데, 아직 스스로 작성하는데 어려움을 느끼는 것은 제대로 알고 있지 않기 때문이다 .. 

 

우선 위의 코드가 옳은 이유는

preorder의 가장 앞에 있는 노드가 root에 위치하고,

inorder에서 preorder에 가장 앞에 있던 값 기준으로 왼쪽은 left subtree, 오른쪽은 right subtree에 속하는 원소들이다.

이것이 재귀적으로 성립하기 때문에 위의 코드는 옳다.