[LeetCode]Construct Binary Tree from Preorder and Inorder Traversal

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

문제 분석

전위 순회, 중위 순회 순서를 가지고 Binary Tree를 복구(생성)하는 문제입니다.

 

처음 시도한 답안

# 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]:
        # https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/748301/python3-solution-with-a-detailed-explanation-preorder-and-inorder-traversal/
        # https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/34579/Python-short-recursive-solution./comments/32947/

        # 기본적으로 전위 순회의 첫번째 값은 부모노드이고, 중위 순회 결과를 left, rigth로 나누는 역할을 한다.
        # 전위 순회의 값을 순차적으로 pop left 하면서 중위 순회를 left, right로 나눈다.

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

        # 순회할 요소가 남아있다면
        if inorder:
            val = preorder.pop(0)
            root = TreeNode(val)

            ind = inorder.index(val)

            # preorder에서 pop한 값을 기준으로 inorder 왼쪽은 왼쪽 자식 트리
            root.left = self.buildTree(preorder, inorder[0:ind])
            # preorder에서 pop한 값을 기준으로 inorder 오른쪽은 오른쪽 자식 트리
            root.right = self.buildTree(preorder, inorder[ind+1:])

            return root

접근 방법

1. 전위 순회와 중위 순회를 알고 있으면 이진 트리를 복원할 수 있습니다.
2. 전위 순회의 값은 중위 순회 결과를 Left 트리와 Right 트리로 나누게 됩니다.
3. 따라서, 전위 순회 결과에서 pop left 하고 해당 값으로 루트 노드를 만듭니다.
4. 중위 순회 결과에서 pop left한 값을 기준으로 루트의 왼쪽 자식, 루트의 오른쪽 자식 노드를 만들고 재귀적으로 호출합니다.
5. 중위 순회를 더이상 순회할 수 없다면, 이진트리가 복원됭 상태입니다.

 

아래의 예시는 다음과 같이 순회하면서 트리를 생성합니다.

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

1. preorder pop left(root) : 3, inorder_left = [9], inorder_right = [15,20,7]
   1. (inorder_left), pop left(root.left) : 9, inorder_left = [], inorder_right = []
   2. (inorder_right), pop left(root.right) : 20, inorder_left = [15], inorder_right = [7]
      1. (inorder_left), pop left(root.left) : 15, inorder_left = [], inorder_right = [] 
      2. (inorder_right), pop left(root.right) : 7, inorder_left = [], inorder_right = []