Published:
Updated:

  • index ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄λ„ 됨
  • collections.deque(preorder).popleft()λ₯Ό μ‚¬μš©ν–ˆμ–΄μ„œ 계속 였λ₯˜κ°€ λ°œμƒν–ˆλ˜ κ±°μ˜€μŒ
    • μ΄λŠ” λ”°λ‘œ λ‚΄μž₯ ν•¨μˆ˜λ₯Ό λ§Œλ“€μ–΄μ„œ dequeλ₯Ό λŒμ•„μ£Όκ²Œλ” ν•˜λŠ” λ°©μ‹μœΌλ‘œ ν•΄κ²°ν•  수 있음
    • 이 식은 계속 μƒˆλ‘œμš΄ dequeλ₯Ό λ§Œλ“ λ‹€λŠ” 것


SolutionPermalink

# 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


ReferencePermalink

Leave a comment