비선형 자료구조 - 트리 ll
해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.
가장 긴 동일 값의 경로
동일한 값을 지닌 가장 긴 경로를 찾아라.
Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).
- 풀이: 상태값 거리 계산 DFS
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
result: int = 0
def longestUnivaluePath(self, root: TreeNode) -> 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
이진 트리 반전
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
- 풀이: 파이썬 다운 방식
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root:
root.left, root.right = \
self.invertTree(root.right), self.invertTree(root.left)
return root
return None
재귀함수를 이용한 방법으로, 지정하는 left와 right를 바꿔주기만 하면 되는 아주 심플한 코드이다.
- 풀이: 반복 구조로 DFS
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
stack = collections.deque([root])
while stack:
node = stack.pop()
# 부모 노드 부터 하향식 스왑
if node:
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root
데크를 이용한 풀이이다. 데크는 이중 연결 리스트이기 때문에 스택에도, 큐에도 자유롭게 활용이 가능하다.
두 이진 트리 병합
두 이진 트리를 병합하라.
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
- 풀이: 재귀 탐색
import collections
# 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
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 and root2:
node = TreeNode(root1.val + root2.val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
else:
return root1 or root2
이진 트리 직렬화 & 역직렬화
이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
- 풀이: 직렬화 & 역직렬화 구현
import collections
class Codec:
# 직렬화
def serialize(self, root: TreeNode) -> str:
queue = collections.deque([root])
result = ['#']
# 트리 BFS 직렬화
while queue:
node = queue.popleft()
if node:
queue.append(node.left)
queue.append(node.right)
result.append(str(node.val))
else:
result.append('#')
return ' '.join(result)
# 역직렬화
def deserialize(self, data: str) -> TreeNode:
# 예외 처리
if data == '# #':
return None
nodes = data.split()
root = TreeNode(int(nodes[1]))
queue = collections.deque([root])
index = 2
# 빠른 런너처럼 자식 노드 결과 먼저 확인 후 큐 삽입
while queue:
node = queue.popleft()
if nodes[index] is not '#':
node.left = TreeNode(int(nodes[index]))
queue.append(node.left)
index += 1
if nodes[index] is not '#':
node.right = TreeNode(int(nodes[index]))
queue.append(node.right)
index += 1
return root
균형 이진 트리
이진 트리가 높이 균형(Height-Balanced, 모든 노드의 서브 트릐 간의 높이 차이가 1 이하)인지를 판단하라.
Input: root = [3,9,20,null,null,15,7]
Output: true
- 풀이: 재귀 구조로 높이 차이 계산
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def check(root):
if not root:
return 0
left = check(root.left)
right = check(root.right)
# 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
if left == -1 or \
right == -1 or \
abs(left - right) > 1:
return -1
return max(left, right) + 1
return check(root) != -1
최소 높이 트리
노드 개수와 무방향 그래프를 입력받아 트리가 최소 높이가 되는 루트의 목록을 리턴하라.
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
- 풀이: 단계별 리프 노드 제거
import collections
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n <= 1:
return [0]
# 양방향 그래프 구성: 무방향 그래프이기에 가능
graph = collections.defaultdict(list)
for i, j in edges:
graph[i].append(j)
graph[j].append(i)
# 첫 번째 리프 노드 추가: 리프 노드 제거에 사용될 변수
leaves = []
for i in range(n + 1):
if len(graph[i]) == 1:
leaves.append(i)
# 루트 노드만 남을 때까지 반복 제거
while n > 2:
n -= len(leaves)
new_leaves = []
for leaf in leaves:
neighbor = graph[leaf].pop()
graph[neighbor].remove(leaf)
if len(graph[neighbor]) == 1:
new_leaves.append(neighbor)
leaves = new_leaves
return leaves
