Leetcode 문제
이번에 풀어볼 문제는 리트코드 105번 문제 Construct Binary Tree from Preorder and Inorder Traversal 이다.
우선 문제를 살펴보자.
리트코드 105번 문제 Construct Binary Tree from Preorder and Inorder Traversal 링크
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
Construct Binary Tree from Preorder and Inorder Traversal - LeetCode
Can you solve this real interview question? 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
leetcode.com
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.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
문제 설명
문제에 대해 간략히 살펴보자. 우선 용어 정리가 필요할 것 같다.
'Tree traversal'란 tree안에 존재하는 모든 node에 방문하는 것이다. 필요하다면 각 노드 방문 시 특정 연산을 수행할 수도 있다. 기본적으로 tree 구조는 선형 구조가 아니기 때문에 모든 노드를 방문하는데 다양한 방법이 존재한다.
다음으로 'Preorder traversal'에 대해 알아보자. 여기서 preorder란 뜻은 tree 구조에서 각 노드를 방문하는데 있어 root 노드를 먼저 방문하고 그 후 왼쪽 subtree 그리고 오른쪽 subtree를 방문하는 것이다. 예를 들어 아래 경우와 같이 tree가 존재할 경우 preoder는 [1, 2, 4, 5, 3]이 된다. 즉 subtree인 3과 sub-subtree인 4를 비교했을 때 preorder에서는 왼쪽에 있는 4가 우선된다는 것이다.
마지막으로 'Inorder traversal'에 대해 알아보자. 여기서 Inorder란 뜻은 tree 구조에서 가장 밑단에 위치한 subtree의 왼쪽에서 탐색을 시작하라는 뜻이다. 즉, 가장 밑단 subtree의 왼쪽 노드 방문 후 그 root를 방문하고 그 다음 그 root의 오른쪽 node를 방문하라는 것이다. 예를 들어 위와 같은 tree 구조가 있을 때 inorder traversal은 [4, 2, 5, 1, 3]이 된다.
이 문제에서 요구하는 바는 preorder와 inorder를 나타내는 두 개의 배열이 주어졌을 때 그 둘에 부합하는 tree 구조를 찾으라는 것이다. Preorder와 inorder에 대한 정의를 정확히 알고 있다면 문제를 이해하는데 어렵지 않을 것이다.
문제 접근법
이 문제에 접근하는 방법은 우선 preorder의 가장 첫번째 값 부터 찾아보는 것이다.
그 이유는 preorder의 정의에 따라 preorder 리스트의 첫번째 값은 tree 가장 상단에 위치하는 root이기 때문이다.
가장 상단에 위치하는 값을 찾은 후 inorder 리스트를 살펴보자.
Inorder 리스트의 정의에 따라 왼쪽 subtree -> root -> 오른쪽 subtree 순으로 구조를 이룬다.
따라서 preorder의 첫번째 값 (=가장 상단 root)을 기준으로 왼쪽에 있는 값들은 왼쪽 subtree,
그리고 오른쪽에 있는 값들은 오른쪽 subtree에 위치함을 알 수 있다.
이 과정을 반복해 나가다 보면 전체 tree 구조를 파악할 수 있다.
문제 예시 1번을 가지고 설명해 보자.
예시에서 주어진 것 처럼 preorder와 inorder가 다음과 같이 주어졌다고 생각해 보자.
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
설명한대로 preorder에서 가장 첫번째 값 (=3)은 tree의 가장 상단 root다.
이때 Inorder 리스트를 살펴보면 3을 기준으로 왼쪽에 있는 값은 9다.
따라서 9는 3을 root로 하는 트리의 왼쪽 subtree에 위치함을 알 수 있다.
동시에 inorder 리스트에서 3을 기준으로 오른쪽에 있는 값들 [15, 20, 7]은 subtree 오른쪽에 있음을 알 수 있다.
이때 오른쪽 subtree에 대해 좀 더 자세히 알아보자.
오른쪽 subtree에 대해 다시 preorder를 살펴보면 3과 9 다음에 오는 값은 20이다.
따라서 오른쪽 subtree의 root는 20임을 알 수 있다.
이때 다시 inorder 리스트를 살펴보면 20을 기준으로 15는 왼쪽에 7은 오른쪽에 있음을 알 수 있다.
결과적으로 root 20을 기준으로 왼쪽 subtree는 15 오른쪽 subtree는 7임을 알 수 있다.
Tree 깊이에 상관 없이 이 과정을 recursive하에 반복하다보면 전체 tree 구조를 파악할 수 있다.
이제 코드로 한 번 살펴보자.
문제 풀이
우선 binary 트리 구조를 정의해준다. (line 2-6)
이 표현 방식은 파이썬에서 가장 일반적으로 사용되는 방식이다.
트리 구조 정의 후 preorder와 inorder를 입력받을 함수를 정의해 준다. (line 8)
만약 입력값 중 하나라도 존재하지 않는다면 None 리턴 후 종료해준다. (line 9)
앞서 설명한대로 preorder 리스트의 첫번째 값은 전체 트리의 가장 상단 root다. (line 13)
Preorder의 첫번째 값은 전체 tree의 root로 지정해준다. (line 14)
그 후 root 값에 해당하는 인덱스를 inorder 리스트에서 찾아준다. (line 17)
앞서 설명한대로 이 값을 기준으로 inorder 리스트 왼쪽은 왼쪽 subtree 오른쪽은 오른쪽 subtree를 나타낸다.
따라서 왼쪽과 오른쪽 subtree의 root값을 찾아준다. (line 20-21)
이 부분이 가장 중요한데 각 subtree의 root 값을 찾아주는데 있어 recursive 함수로 찾아준다.
그 이유는 우리는 tree의 깊이가 얼마나 깊은지 모르기 때문이다.
이때 중요한 것은 recursive 하게 찾아줌에 있어 왼쪽 subtree는 앞서 찾은 root 값 왼쪽으로만 탐색을 하고
오른쪽 subtree는 앞서 찾은 root 값 오른쪽으로만 해야한다는 것이다.
이 과정을 반복하다보면 전체 tree 구조를 만들 수 있다.
문제 풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# 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
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
# The first element of preorder is the root
root_val = preorder.pop(0)
root = TreeNode(root_val)
# Find the index of the root in inorder
inorder_idx = inorder.index(root_val)
# Build left and right subtrees
root.left = buildTree(preorder, inorder[:inorder_idx])
root.right = buildTree(preorder, inorder[inorder_idx+1:])
return root
# Example usage:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
|
cs |
관련 문제
리트코드 98번 Validate binary search tree 문제 풀이 (링크)
리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)
리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)
리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)
리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)
리트코드 212번 Word search 2 문제 풀이 (링크)
리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)
리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)
리트코드 572번 Subtree of another tree 문제 풀이 (링크)
