[코딩테스트 Python3 (5)] Tree 트리 자료구조 - BFS / DFS

재귀함수 Recursive Function

재귀함수(Recursive Function)란 자신을 정의할 때 자기 자신을 재참조하는 함수

시간복잡도

재귀함수 전체 시간복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나당) 시간복잡도

Execution Tree(recursion tree): 재귀함수의 실행흐름을 나타내는 데 사용하는 트리

O(n) : n에 비례한 호출 → recurrence relation : f(n) = f(n-1) + n

O(2^n) : 2^n에 비례한 호출 → recurrence relation : f(n) = f(n-1) + f(n-2)

Tree

Tree는 서로 연결된 Node의 계층형 자료구조로써, roor와 부모-자식 관계의 subtree로 구성되어 있습니다.

차수(degree): 각 노드가 갖는 자식의 수. 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다.

→ 위와 같은 경우에 degree = 2

조상(ancestor): 위쪽으로 간선을 따라가면 만나는 모든 노드

자손(descendant): 아래쪽으로 간선을 따라가면 만나는 모든 노드

높이(height): 루트노드에서 가장 멀리 있는 리프 노드까지의 거리. 즉, 리프 노드 중에 최대 레벨 값

→ 위와 같은 경우에 height = 3

class Node:
	def __init__(self, value = 0, left = None, right = None):
    	self.value = value
        self.left = left
        self.right = right
        
class BinaryTree:
	def __init__(self):
    	self.root = None

bt = BinaryTree()
bt.root = Node(value = 1)
bt.root.left = Node(value = 2)
bt.root.right = Node(value = 3)
bt.root.left.left = Node(value = 4)
bt.roor.left.right = Node(value = 5)
bt.root.right.right = Node(value = 6)

트리 순회 Tree Traversal

트리 탐색(search)이라고도 불리우며 트리의 각 노드를 방문하는 과정을 말한다. 모든 노드를 한 번 씩 방문해야 하므로 완전탐색이라고도 불린다. 

순회 방법으로는 너비 우선 탐색의 BFS(Breadth-first search)와 깊이 우선 탐색 DFS(Depth-first search)가 있다.

BFS(Breadth-first search)

def bfs(root):
    visited = []
    if root is None:
    	#빈 리스트를 반환
    	return []
    #추가적으로 방문해야 하는 node에 대한 정보를 저장
    q = deque()
    q.append(root)
    while q:
    	cur_node = q.popleft()
        visited.append(cur_node.value)
        
        if cur_node.left:
        	q.append(cur_node.left)
        if cur_node.right:
        	q.append(cur_node.right)
    return visited
bfs(root)

DFS(Depth-first search)

def dfs(cur_node):
	if cur_node is None:
    	return 
    dfs(cur_node.left)
    dfs(cur_node.right)

dfs(root)

전위순회(pre-order) / 중위순회(in-order) / 후위순회(post-order)

[Post-order] Lowest Common Ancestor of a Binary Tree

---

코테 적용 방법

Tree 활용
1. Tree 구현
2. Tree 순회
    a. level order
    b. post order

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

[BFS - Level order traversal] Maximum Depth of Binary Tree

시간 복잡도 → 노드의 개수 만큼 O(n)

from collections import deque
#level order 순회 방식으로 해결함
def maxDepth(root):
    max_depth = 0
    if root is None:
    	return max_depth
    q = deque()
    q.append((root, 1))
    while q:
    	cur_node, cur_depth = q.popleft()
        max_depth = max(max_depth, cur_depth)
        if cur_node.left:
        	q.append((cur_node.left, cur_depth + 1))
        if cur_node.right:
        	q.append((cur_node.right, cur_depth + 1))
    return max_depth

#post-order 방식으로 해결함
def maxDepth(root):
    max_depth = 0
    
    if root is None:
    	return max_depth
        
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    max_depth = max(left_depth, right_depth) + 1
    return max_depth
    
maxDepth(root)

[BFS] 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75 

Leaf-Similar Trees - LeetCode

# 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
from collections import deque
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        #BFS가 아니라 DFS 문제라는 것을 깨달음
        def dfs(root):
            if root is None: 
                return []
            if not root.left and not root.right:
                return [root.val]
            return dfs(root.left) + dfs(root.right)
        return dfs(root1) == dfs(root2)​

 

출처

https://inf.run/wVz9

코딩테스트 [ ALL IN ONE ] - 인프런 | 강의