[leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal

문제 설명

링크
preorder, inorder 로 쓰여진 배열을 보고 bst 를 만드는 문제

접근 1 - Recursion

• preorder[0] 은 root
• inorder 에서 root 를 기준으로 왼쪽은 left child, 오른쪽은 right child 로 나뉨을 이용
• 재귀로 트리 만듬

코드 1

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        left = right = None 
        num = len(preorder)
        if num == 0: return left
        
        root = TreeNode(preorder[0])
        if num == 1: return root
        elif num == 2:
            if preorder == inorder:
                right = TreeNode(preorder[1])
            else:
                left = TreeNode(preorder[1])
        else:
            rootIdx = inorder.index(root.val)
            left = self.buildTree(preorder[1:rootIdx + 1], inorder[:rootIdx])
            right = self.buildTree(preorder[rootIdx+1:], inorder[rootIdx+1:])
        root.left = left
        root.right = right 
        return root

접근 2 - Recursion 응용

• 매번 root 값의 index 를 inorder 에서 찾기위해 시간이 소요됨
• inorder 와 preorder 를 pop 하면서 재귀 진행
• pop 을 효율적으로 하기 위해 inorder,preorder 배열을 reverse 시킴
• inorder 에서 3을 만나기전까지는 left, 이후는 right

코드 2

class Solution:
    def buildTree(self, preorder, inorder):
        def build(stop):
            if inorder and inorder[-1] != stop:
                root = TreeNode(preorder.pop())
                root.left = build(root.val)
                inorder.pop()
                root.right = build(stop)
                return root
        preorder.reverse()
        inorder.reverse()
        return build(None)