[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal (Python)

• index 함수를 사용해도 됨
• collections.deque(preorder).popleft()를 사용했어서 계속 오류가 발생했던 거였음
  • 이는 따로 내장 함수를 만들어서 deque를 돌아주게끔 하는 방식으로 해결할 수 있음
  • 이 식은 계속 새로운 deque를 만든다는 것

Solution

# Definition for a binary tree node.
import collections
from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    # 주어진 inorder, preorder 값으로 트리 만드는 문제
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None

        # preorder ALWAYS has the node first.
        # But you don't know the size of either branch.
        pre_popleft = preorder.pop(0)
        # pre_popleft = collections.deque(preorder).popleft()

        # inorder ALWAYS has the left branch to the left of the node
        # and right branch to the right of the node.
        # So now you know the size of each branch.
        index = 0
        for x in inorder:
            if x == pre_popleft:
                break

            index += 1

        node = TreeNode(inorder[index])

        node.left = self.buildTree(preorder, inorder[:index])
        node.right = self.buildTree(preorder, inorder[index + 1:])

        return node

Reference

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