(6) Tree
Tree는 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어 있습니다.
Tree Traversal(순회)은 BFS, DFS로 나뉩니다.
BFS는 큐로 구현되며, DFS는 반복문+stack 혹은 recursion으로 구현됩니다.
BFS와 DFS에 들어가기 앞서, 먼저 recursion과 이진트리(binary tree)에 대해 살펴보겠습니다.
(1) Recursion
재귀함수는 (1) 점화식에 recurrence relation이 있어야 하며 (2) 재귀 호출에 빠져나올 조건인 base case가 있어야 합니다.
대표적인 재귀함수로는 factorial과 fibonacci가 있습니다.
Recursion의 시간복잡도
- factorial 점화식은 O(n)이고, factorial() 함수의 시간복잡도와 곱한 값이 최종 시간복잡도입니다.
- fibonacci 점화식은 O(2^n)이고, fibonacci() 함수의 시간복잡도와 곱한 값이 최종 시간복잡도입니다.
(2) 이진트리 (Binary Tree)
Tree에서 degree란, 노드의 차수를 말하고
모든 노드의 차수가 n개 이하인 트리를, “n진 트리”라고 합니다.
여기에서, 모든 노드의 차수가 2개이면 완전이진트리(complete binary tree)라고 하며, 이는 heap 자료구조에서 볼 수 있습니다.
엄밀히 말하면, 트리에서는 BFS, DFS가 없고 level order, post order라고 합니다.
하지만, 개념이 같기 때문에 트리에서도 편의상 BFS와 DFS라고 하겠습니다.
(3) BFS by Queue
앞서 설명한, tree를 순회하는 방법 중 하나로 트리의 상위 레벨부터 하나씩 순회하는 level order 방법입니다.
템플릿처럼 외워야합니다!!
# 가장 간단한 BFS, 방문순서 list로 변환해주기
from collections import deque
def bfs(root):
visited = []
if root is None: return []
q = deque()
q.append(root)
while q:
cur_node = q.popleft() # 접근(access)
visited.append(cur_node.value) # 방명록 남기기, 방문 (트리에서 visitied는 필수가 아님!)
if cur_node.left:
q.append(cur_node.left)
if cur_node.right:
q.append(cur_node.right)
return visited
(4) DFS by Recursion
DFS를 구현하는 방법은 2가지 입니다.
- stack + 반복문
- 재귀
재귀로 짤 경우 코드가 간단해지므로, 재귀로 짜는 방식을 선호하겠습니다.
def dfs(root):
if root is None: # base case
return
dfs(root.left) # subtree의 새로운 root가 됨.
dfs(root.right)
dfs(root)
1. 접근과 방문은 다르다
Tree를 순회한다는 것은 접근하여 방문하는 것입니다.
헷갈리지 맙시다! 접근(access)과 방문은 다릅니다. 보통, DFS에서는 접근을 여러번 하게 되고, 방문은 한 번 하게 됩니다. 방문은 어떤 작동을 시키는 것을 의미합니다.
2. 접근 방식
- left child부터 파고 들기
- right child부터 파고 들기
3. 방문 방식
- 전위순회(preorder) : child 접근 전 방문 A B D G H E C F
- 중위순회(inorder) : left 우선 접근방식이면, right child 접근 전 방문 G D H B E A C F
- 후휘순회(postorder) : child 접근 후 방문 G H D E B F C A
(5) Tree를 사용하는 경우
Tree 구현
Tree 순회 ⭐
- level order (BFS)
- post order (DFS)
🍓 Lowest Common Ancestor 문제
- 접근 방법 : p와 q의 부모 노드의 공통 분모 중 가장 작은 거 구해야 하니까, 아래에서 정보가 올라와야 합니다.
- postorder 순회 방식
- 시간 복잡도 : 순회 O(n)
# from collections import deque
# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# # Make tree.
# def array2tree(arr):
# q = deque()
# root = TreeNode(arr[0])
# q.append(root)
# idx = 1
# while idx < len(arr):
# cur_node = q.popleft()
# # left node
# if arr[idx] != None:
# cur_node.left = TreeNode(arr[idx])
# q.append(cur_node.left)
# idx += 1
# # right node
# if arr[idx] != None:
# cur_node.right = TreeNode(arr[idx])
# q.append(cur_node.right)
# idx += 1
# return root
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: int, q: int) -> int:
if root is None:
return None
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if root.val == p or root.val == q: # root는 cur_node
return root.val # leetcode에서는 p와 q가 int가 아닌 TreeNode이므로 root를 리턴해야 함.
elif left and right:
return root.val
return left or right
root = array2tree([3,5,1,6,2,0,8,None,None,7,4])
sol = Solution()
print(sol.lowestCommonAncestor(root, 5,1))
🍓 Max Depth 문제
- 접근 방법 1 : 위에서 아래로 depth += 1
- Level order (BFS)
- 시간 복잡도 : 순회 O(n)
class Solution: def maxDepth(self, root) -> int: max_depth = 0 if root == None: return max_depth q = deque() q.append((root, 1)) while q: cur, depth = q.popleft() if cur.left: q.append((cur.left, depth+1)) # 방문예약 if cur.right: q.append((cur.right, depth+1)) # 방문예약 max_depth = max(max_depth, depth) return max_depth - 접근 방법 2 : 아래에서 위로 depth += 1
- Post order (DFS)
- 시간 복잡도 : 순회 O(n)
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root == None: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return max(left_depth, right_depth) + 1
어떤 순회든 시간복잡도는 O(n) 입니다.
다음에는 Graph에 대해서 포스팅 하겠습니다 :)
해당 시리즈의 포스트는 인프런에서 제공하는 개발남노씨의 코딩테스트 강의 를 바탕으로 작성하였습니다.
Leave a comment