leetcode 105

해당 문제는 재귀와 함께 생각을 잘못해서 처음에 202번째 testcase에서 계속 오류가 났었다.

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, inorder):
        
        if len(inorder) == 0:
            return 
        # print(preorder,inorder)
        root_value = preorder.pop(0)
        root_index = inorder.index(root_value)
        root = TreeNode(root_value)
        # lefts = [val for val in preorder if val in set(inorder[:root_index])]
        # rights = [val for val in preorder if val in set(inorder[root_index+1:])]
        root.left = self.buildTree(preorder,inorder[:root_index])
        root.right = self.buildTree(preorder,inorder[root_index+1:])
        
        return root 

위 buildTree 함수에 lefts와 rights를 따로 만드는 과정을 진행해서 root child 의 buildTree 함수에서 parameter에 사용하려고 했습니다. 이렇게 생각했던 이유는 트리의 재귀적인 구조 때문에 left의 하위 노드들과, right의 하위 노드들을 구분시켜 넘겨줘야한다고 생각했습니다.

하지만, 재귀적인 특성 때문에 preorder 리스트에 있는 값들을 하나씩 접근해서 inorder의 정보들만 slice해서 넘겨주는 게 좋다고 생각이 들었습니다.
이유
1. inorder는 root node를 기준으로 왼쪽은 left, 오른쪽은 right의 하위 노드임이 자명하다.
2. 하지만 preorder는 그러하지 않기에 preorder는 pop을 통해 현재 root 노드를 찾는 것이 좋다고 판단했다.