문제 링크

나의 논리

지난번에 백준에서 푼 문제인데 정답을 보고 풀었던것 같다.
역시나 이번에도 풀지 못했다. 그러나 문제 풀이에 핵심적인 아이디어는 떠올랐으니..발전하긴 하는것 같다.

전위순회와 중위순회를 이용해서 트리를 만드는 문제다. 문제에서
전위순회 preorder = [3,9,20,15,7]
후위순회 inorder = [9,3,15,20,7]이다.

전위순회의 정의는 노드 방문 -> 왼쪽 노드 -> 오른쪽 노드
후위순회의 정의는 왼쪽 노드 -> 노드 방문 -> 오른쪽 노드

즉 전위순회 리스트는
[root node, ... 루트노드 왼쪽 서브트리에 있는 모든 노드들 ... , ... 루트노드 오른쪽 서브트리에 있는 모드 서브트리들의 노드들 ... ] 이다.

중위순회의 리스트는
[왼쪽 서브트리의 모든 노드들 ... , 루트 노드, ... 오른쪽 서브트리의 모든 노드들 ] 이다.

그래서 전위순회 리스트에서 루트노드를 먼저 찾고 리스트에서 루트노드를 없앴다. 중위순회 리스트에서 루트노드를 기준으로 어디서 어디부터가 왼쪽 서브트리, 오른쪽 서브트리인지 찾는다. 그리고 재귀적으로 서브트리를 넘겨주고, 전위순회 리스트에서 또 첫번째 값은 루트노드이므로 위의 과정을 반복한다.

중요한 점은 트리순회는 왼쪽부터 방문하여야 하므로 코드도 왼쪽 서브트리를 만들고 오른쪽 서브트리를 만들어야 한다.

중위순회는 왼쪽 서브트리 또는 오른쪽 서브트리에 해당하는 서브리스트를 넘겨주지만, 전위순회리스트는 루트노르를 제외한 나머지를 모두 넘겨준다.

왼쪽 서브트리부터 만듦으로
루트노드.left_subtree(preorder, inorder[left_subtree]처럼 해줘야한다.

처음에 좀 햇갈린 부분이 preorder에서 첫번째 원소가 왼쪽 서브트리에 있는 원소가 아니면 어떡하냐? 였는데 그런 걱정은 안해도된다.
루트노드+1 +n 까지는 전위순회의 정의에 의해서 무조건 왼쪽 서브트리들의 노드들만 가지게 된다.

왼쪽 서브트리를 다 만들고 재귀로부터 돌아오면 preoder에는 오른쪽 서브트리의 노드들만 가지게 된다.

정답 코드

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        
        if not inorder:
            return None
        
        index = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[index])
        root.left = self.buildTree(preorder, inorder[:index])
        root.right = self.buildTree(preorder, inorder[index+1:])
        
        return root