트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로, 루트값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.
트리는 하나의 뿌리(Root)에서 위로 뻗어나가는 형상처럼 생겨서 ‘트리(나무)’라는 명칭이 붙었다.
실생활에서 볼 수 있는 트리구조에는 족보, 회사의 조직도 등이 있다.
좀더 중요한 트리의 속성은 재귀로(recursively) 정의된 자기 참조(self-Referential) 자료구조라는 점이다. 즉. 자식도 , 자식의 자식도, 모두 트리이며, 트리가 여러개 쌓여 큰 트리가 된다.
이러한 재귀적 특성 덕에 트리에서는 재귀 순회가 더 자연스러운 편이다.
“트리는 순환구조를 갖지 않는 그래프입니다.”
그래프와 트리의 차이점에서 핵심은 순환구조가 아니라는데 있다.
트리는 특수한 형태의 그래프의 일종이며, 크게 그래프의 범주에 포함된다.
하지만, 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다.
이외에도 단방향(Uni-Directional), 양방향(Bi-Directional)을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.
그뿐만 아니라 트리는 하나의 부모 노드를 갖는 다는 차이점이 있으며, 루트 또한 하나여야 한다.
“이진 트리요?”
우리는 “트리”하면, “이진트리”가 떠오르는데, 그것이 뭔지 정확히는 알지 못한다.
왜냐면, “왜”와 “정의” 두가지를 놓치고 있기 때문이다.
트리중에서 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree)다.
먼저, 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 혹은 다진트리)
여기서 m=2이면, 즉, 모든 노드의 차수(자식의 개수)가 2이하이면, 특별히 이진 트리(Binary Tree)라고 구분해서 부른다.
2진 트리는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결하며 여러가지 알고리즘을 구현하는 일도 좀더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진 트리를 일컫는다.
이진 트리 유형
이진 트리의 최대 깊이를 구하라.
본 문제는 주어진 이진 트리에 대해 최대 깊이를 구하는 문제이다.
본 책에서는, BFS(너비 우선 탐색)으로 풀이 했다.
# Definition for a binary tree node.
import collections
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def maxDepth(self, root: TreeNode) -> int:
"""
:type root: TreeNode
:rtype: int
"""
queue = collections.deque([root])
depth = 0
# queue에서 같은 레벨의 부모 노드들을 pop할 때마다 깊이 1 추가
while queue:
depth += 1
# queue, 즉, 부모 노드 큐 길이만큼 반복하므로,
# 그 뒤에 들어간 자식노드는 다음 주기에서 반복
for _ in range(len(queue)):
cur_root = queue.popleft()
if cur_root.left:
queue.append(cur_root, left)
if cur_root.right:
queue.append(cur_root.right)
return depth
이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라.
본 트리에서, 가장 긴 경로는 4→2→1→3 혹은, 5→2→1→3이다.
가장 긴 경로를 찾기 위해서는, 루트 노드에서 이진트리의 left, right의 리프 노드까지의 거리들을 더하면 된다.
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
longest: int = 0
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(node: TreeNode) -> int:
# 예외 처리
if not node:
return -1
# 왼쪽, 오른쪽의 각 리프 노드까지 탐색
left = dfs(node.left)
right = dfs(node.right)
#현재 노드가 루트 노드인 이진트리에서 가장 긴 경로
self.longest = max(self.longest, left+right+2)
# 상태값(현재 노드를 루트 노드로 하는 트리의 리프노드에서 현재 노드 까지의 거리)
return max(left, right)+1
dfs(root)
return self.longest
본 문제에서는, 먼저 리프노드까지 도달한 이후, 부모 노드로 거슬러 올라 가면서 각각의 거리를 계산해 상태값을 업데이트하면서 다음과 같이 누적해나갔다.
-1은 존재하지 않는 노드에 부여되는 일종의 페널티이다.
이때, 상태값은 리프 노드에서 현재 노드까지의 거리이며,
거리는 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값이다.
동일한 값을 지닌 가장 긴 경로를 찾아라.
Input: root = [5,4,5,1,1,5]
Output: 2
Input: root = [1,4,5,4,4,5]
Output: 2
동일한 값을 지닌 노드 간의 이동거리가 가장 긴 경로를 찾는 문제였다.
43번의 풀이와 같이, dfs로 리프노드까지 탐색해 내려간 뒤, 부모노드와 값이 일치할 경우 거리를 차곡차곡 쌓아 올려가며 백트래킹 하는 형태로 풀이할 수 있다.
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
result: int = 0
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(node: TreeNode):
if node is None:
return 0
# 존재하지 않는 노드까지 DFS 재귀 탐색
left = dfs(node.left)
right = dfs(node.right)
# 현재 노드가 자식 노드와 동일한 경우 거리 1 증가
if node.left and node.left.val == node.val:
left += 1
else:
left = 0
if node.right and node.right.val == node.val:
right += 1
else:
right = 0
# 왼쪽과 오른쪽 자식 노드 간 거리의 합 최댓값이 결과<표시>
self.result = max(self.result, left + right)
# 자식 노드 상태값 중 큰 값 리턴
return max(left, right)
dfs(root)
return self.result
위 풀이에서, <표시> 부분과 dfs의 return 값이 다른 이유는,
경로를 따질 때, left의 리프부터 부모 노드를 거쳐 right의 리프노드로 가는 경로가 있다고 가정해 보면, 현재 부모노드의 부모노드로 거슬러 올라가면, 해당 경로가 성립이 불가능하기 때문이다.
따라서 return 값으로 left와 right중 더 큰 상태값을 return 하는 것이다.
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]