전위, 중위 순회 결과를 이용해 이진 트리 구축

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

 순회에는 크게 전위, 중위, 후위 순회가 있으며 이 셋 중 2가지만 있어도 이진 트리를 복원할 수 있다.

 위 그림에서 전위의 첫 번째 값은 부모 노드이다. 즉 전위 순회의 첫 번째 결과는 정확히 중위 순회 결과를 왼쪽과 오른쪽으로 분할시키는 역할을 한다. 

 왼쪽 노드의 2는 중위 순회 결과를 정확히 반으로 가르고, 각각 왼쪽 자식은 4, 오른쪽 자식은 5로 마무리한다.

 

 먼저 전위 순회 첫 번째 결과를 가져와 중위 순회를 분할하는 인덱스로 한다. 이 값을 현재 노드로 구성하고, 이를 기준으로 중위 순회 결과를 쪼개서 왼쪽, 오른쪽으로 각각 마무리될 때 분할 정복 구조로 재귀 호출하면, 트리를 구성할 수 있다.

# 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]) -> Optional[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