반응형
Notice
Recent Posts
Recent Comments
- Today
- Total
작심삼일
[LeetCode] 105 | Construct Binary Tree from Preorder and Inorder Traversal | Python 본문
스터디/코테
[LeetCode] 105 | Construct Binary Tree from Preorder and Inorder Traversal | Python
yun_s 2022. 7. 14. 09:47728x90
반응형
문제 링크: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
문제
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
조건
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of inorder also appears in preorder.
- preorder is guaranteed to be the preorder traversal of the tree.
- inorder is guaranteed to be the inorder traversal of the tree.
내 풀이
Inorder는 왼쪽 $\rightarrow$ 오른쪽 $\rightarrow$ root 순서로 탐색한다.
Preorder는 root $\rightarrow$ 왼쪽 $\rightarrow$ 오른쪽 순서로 탐색한다.
그렇기때문에 Preorder의 맨 처음 원소(x)는 root가 된다.
Inorder의 처음부터 x까지는 root의 왼쪽이 되고, x부터 끝까지는 root의 오른쪽이 된다.
코드
# Definition for a binary tree node.
# 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: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not inorder: return
idx = inorder.index(preorder.pop(0))
root = TreeNode(inorder[idx])
root.left = self.buildTree(preorder, inorder[:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return root
728x90
반응형
'스터디 > 코테' 카테고리의 다른 글
[LeetCode] 118 | Pascal's Trigangle | Python (0) | 2022.07.19 |
---|---|
[LeetCode] 695 | Max Area of Island | Python (0) | 2022.07.15 |
[LeetCode] 102 | Binary Tree Level Order Traversal | Python (0) | 2022.07.13 |
[LeetCode] 473 | Matchsticks to Square | Python (0) | 2022.07.12 |
[LeetCode] 199 | Binary Tree Right Side View | Python (0) | 2022.07.11 |
Comments