Leetcode 문제
이번에 풀어볼 문제는 리트코드 226번 문제 Invert Binary Tree 다.
우선 문제를 살펴보자.
리트코드 226번 문제 Invert Binary Tree 링크
https://leetcode.com/problems/invert-binary-tree/description/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
문제 설명
문제를 간략히 살펴보자. 인풋으로 binary tree가 주어진다. 이를 invert 하여 그것의 root를 나타내라는 것이 문제에서 요구하는 바다. 문제 예시 1번을 살펴보자. 인풋으로 4를 root로 하는 binary tree가 리스트 형태로 주어진다. 이때 4를 기준으로 binary tree의 왼쪽과 오른쪽을 뒤집으라는 것이 invert의 의미이다. 위의 그림에서 보는 것과 같이 4를 기준으로 뒤집으면 sub-root에 해당하는 2와 7의 위치가 서로 바뀐다. 마찬가지로 sub sub-root에 해당하는 1, 3, 6, 9 역시 4를 기준으로 뒤집히게 되어 9, 6, 3, 1순으로 binary tree에 위치힌다. 문제를 이해하는데 어렵지 않으므로 곧바로 문제를 풀어보도록 하자.
문제 접근법
이 문제는 말 그대로 binary tree의 왼쪽과 오른쪽 node를 서로 바꿔 줌으로서 해결 가능하다.
한 가지 문제는 문제의 조건에 따라 node의 개수가 최대 100개가 될 수 있다는 것이다.
즉, node 개수가 커짐에 따라 sub tree의 깊이가 커져 왼쪽과 오른쪽 node를 어떻게 바꿔야 하나 고민할 수 있다.
이 문제를 해결하기 위해서는 recursive 함수를 이용해야 한다.
즉, binary tree의 root에 대한 sub tree 부터 시작하여 가장 아래쪽 sub tree까지 탐색을 한다.
이 과정을 더 이상 sub tree 혹은 node가 존재하지 않을때 까지 진행한다.
우리는 가장 아래 sub tree에 도착했을 때 왼쪽과 오른쪽 node를 서로 바꿔준다.
그리고 이 과정을 재귀 함수를 이용하여 반복한다.
이 과정을 모두 마치고 나면 왼쪽과 오른쪽에 있는 노드가 서로 invert 되어있음을 알 수 있다.
이제 코드로 한 번 구현해 보자.
문제 풀이
Binary tree 구조를 위한 class를 선언해 준다. (line 1-5)
이는 파이썬에서 일반적으로 사용되는 binary tree 표현식이니 익숙해 지도록 하자.
우리는 왼쪽과 오른쪽 노드를 서로 바꿔주기 위한 (=invert) 함수를 정의해 준다. (line 7)
만약 아무런 노드가 존재하지 않는다면 None을 리턴하고 종료한다. (line 8-9)
우리는 왼쪽 노드에는 오른쪽 노드값을, 오른쪽 노드값에는 왼쪽 노드값을 넣어줄 것이다. (line 10)
이때 값을 넣어주기 전에 재귀함수를 이용하여 그 sub tree의 노드 값들을 먼저 바꿔준다.
앞서 설명했듯이 이 과정은 더 이상 sub tree 혹은 node가 없을때까지 진행한다.
이 과정을 마쳤을때는 root를 기준으로 왼쪽과 오른쪽이 바뀌어 있다.
그리고 마지막에 우리가 찾고자 하는 root 를 리턴하고 종료한다. (line 11)
추가로 binary tree를 만들기 위한 class (line 14-20)와 그것을 출력하기 위한 class (line 23-37)를 선언해줬다.
이 문제에 대한 직접적인 내용은 아니기 때문에 설명은 하지 않겠다.
하지만 파이썬에서 binary 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root
# Helper function to create a binary tree from a list
def createTree(lst, index=0):
if index >= len(lst) or lst[index] is None:
return None
root = TreeNode(lst[index])
root.left = createTree(lst, 2*index + 1)
root.right = createTree(lst, 2*index + 2)
return root
# Helper function to print the tree in level order
def printTree(root):
if not root:
return []
result, queue = [], [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result[-1] is None:
result.pop()
return result
# Example usage
tree1 = createTree([4,2,7,1,3,6,9])
print(printTree(invertTree(tree1))) # Expected output: [4,7,2,9,6,3,1]
tree2 = createTree([2,1,3])
print(printTree(invertTree(tree2))) # Expected output: [2,3,1]
tree3 = createTree([])
print(printTree(invertTree(tree3))) # Expected output: []
|
cs |
관련 문제
리트코드 98번 Validate binary search tree 문제 풀이 (링크)
리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)
리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)
리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)
리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)
리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)
리트코드 212번 Word search 2 문제 풀이 (링크)
리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)
리트코드 572번 Subtree of another tree 문제 풀이 (링크)
