📌 42) 이진 트리의 최대 깊이 ( 리트코드 104. Maximum Depth of Binary Tree )
✔ 풀이 (반복구조로 BFS 풀이)
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
depth = 0
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
#자식 노드가 있을 경우 노드 추가
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth📌 43) 이진 트리의 직경 ( 리트코드 543. Diameter of Binary Tree )
✔ 풀이 (상태값 누적 트리 DFS)
# 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:
distance = 0
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return -1
#왼쪽, 오른쪽 각 리프노드까지 탐색
left = dfs(node.left)
right = dfs(node.right)
#경로의 가장 긴 길이
self.distance = max(self.distance, left + right + 2)
return max(left, right) + 1
dfs(root)
return self.distance📝 중첩함수에서 클래스 변수를 사용한 이유
클래스 변수 사용하지 않고 부모함수 변수를 사용하면 UnboundLocalError: local variable '변수명' referenced before assignment 발생 (할당전에 참조된 지역변수)
중첩함수는 부모함수의 변수를 자유롭게 읽어들일 수 있지만, 부모함수의 변수를 재할당하게 되면 참조 ID가 변경되며 별도의 로컬 변수로 선언됨
✔ 중첩함수에서 부모함수의 변수를 읽기만 경우
def boo():
def boo_in():
print(id(num)) #4347830536출력
print(id(l)) #4351281984출력
return
num, l = 1, []
print(id(num)) #4347830536출력
print(id(l)) #4351281984출력
boo_in()
return
if __name__ == '__main__':
boo()👉 그냥 읽기만 하는 경우에는 참조 ID가 변경되지 않음
✔부모함수의 변수를 재할당하여 조작 (숫자)
def boo():
def boo_in():
num += 1
print(id(num))
return
num = 1
print(id(num))
boo_in()
return
if __name__ == '__main__':
boo()👉UnboundLocalError: local variable 'num' referenced before assignment 발생
만약 숫자나 문자가 아니라 리스트나 딕셔너리 같은 자료형이라면 append()등의 메소드를 이용해 재할당 없이 조작 가능 (숫자,문자 = 불변객체 / 리스트,딕셔너리 = 가변객체 이므로)
✔부모함수의 변수를 재할당 없이 조작 (리스트)
def boo():
def boo_in():
l.append(12)
print(id(l)) #4308552512출력
return
l = []
print(id(l)) #4308552512출력
boo_in()
return l
if __name__ == '__main__':
print(boo()) #[12]출력📌 44) 가장 긴 동일 값의 경로 ( 리트코드 687. Longest Univalue Path )
✔ 풀이 (상태값 거리 계산 DFS)
# 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:
result = 0
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node: #node == None
return 0
#각각 왼쪽, 오른쪽 리프노드까지 내려감 (DFS재귀탐색)
left = dfs(node.left)
right = dfs(node.right)
#값이 같을 경우
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📌 45) 이진 트리 반전 ( 리트코드 226. Invert Binary Tree )
✔ 풀이 (파이썬 다운 방식)
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root:
root.left, root.right = \
self.invertTree(root.right), self.invertTree(root.left)
return root
return None✔ 풀이 (반복 구조로 BFS)
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
q = deque([root])
while q:
node = q.popleft()
if node:
node.left, node.right = node.right, node.left
q.append(node.left)
q.append(node.right)
return root✔ 풀이 (반복 구조로 DFS)
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = 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✔ 풀이 (반복 구조로 DFS 후위 순회)
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = deque([root])
while stack:
node = stack.pop()
if node:
stack.append(node.left)
stack.append(node.right)
node.left, node.right = node.right, node.left
return root📌 46) 두 이진 트리 병합 ( 리트코드 617. Merge Two Binary Trees )
✔ 풀이 (재귀 탐색)
# 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📌 47) 이진 트리 직렬화 & 역직렬화 ( 리트코드 297. Serialize and Deserialize Binary Tree )
✔ 풀이
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import defaultdict
class Codec:
#직렬화 -> 논리적인 구조로 되어있는 이진트리를 배열로(물리적인 구조로) return
def serialize(self, root):
nodes = [None] #인덱스 계산 쉽게 하기 위해 0은 NULL값으로 채우고 인덱스1부터 시작
q = deque([root])
while q:
node = q.popleft()
if node: #node가 None이 아닐경우
nodes.append(node.val)
q.append(node.left)
q.append(node.right)
else: #None일 경우
nodes.append(None)
return nodes
#역직렬화 -> 배열로 되어있는 이진트리를 원래의 논리적인 구조로 return
def deserialize(self, data):
if data == [None, None]: #예외처리
return None
root = TreeNode(data[1])
q, idx = deque([root]), 2 #처음시작 인덱스 1 , 다음 노드는 인덱스 2
while q:
node = q.popleft()
if data[idx] != None: #왼쪽 노드 값 존재할 경우
node.left = TreeNode(data[idx])
q.append(node.left)
idx += 1 #왼쪽 다음 오른쪽노드로 이동
if data[idx] != None: #오른쪽 노드 존재할 경우
node.right = TreeNode(data[idx])
q.append(node.right) #오른쪽 다음 왼쪽 노드로 이동
idx += 1
return root📌 48) 균형 이진 트리 ( 리트코드 110. Balanced Binary Tree )
✔ 풀이 (재귀 구조로 높이 차이 계산)
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
#재귀함수
def check(node):
#리프노드(None)도착
if not node:
return 0
left = check(node.left)
right = check(node.right)
#두 서브트리간의 높이차가 1 이상일 경우 -1 return
#left, right 둘 중 하나라도 -1이면 계속 -1을 return
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return max(left, right) + 1 #둘 중 큰것 + 1 = 상태값
return check(root) != -1📌 49) 최소 높이 트리 ( 리트코드 310. Minimum Height Trees )
✔ 풀이 (단계별 리프노드 제거)
from collections import defaultdict
class Solution:
#최소 높이를 가지는 root return
#최소 높이를 가지는 root는 가운데에 위치해있음
#리프노드를 제거하다 보면 가운데에 있는 노드만 남게됨
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
#그래프 구현
graph = defaultdict(list)
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
#첫번째 리프노드 구하기 -> 리프노드는 그래프에서 길이가 1인 리스트를 값으로 갖음
leaves = []
for key in graph:
if len(graph[key]) == 1:
leaves.append(key)
while n > 2: #가운데 노드만 남을때까지 리프노드 제거
n -= len(leaves)
next_leaves = []
for node in leaves:
#리프노드와 연결되어 있는 노드와 연결상태 제거
neighbor = graph[node].pop()
graph[neighbor].remove(node)
if len(graph[neighbor]) == 1:
next_leaves.append(neighbor)
leaves = next_leaves
return leaves📌 50) 정렬된 배열의 이진 탐색 트리 변환 ( 리트코드 108. Convert Sorted Array to Binary Search Tree)
✔ 풀이 (이진 검색 결과로 트리 구성)
# 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:
#정렬 된 배열을 이진탐색트리 형태로 return
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return
mid = len(nums) // 2 #중앙값
#분할 정복으로 이진 검색 결과 트리 구성
node = TreeNode(nums[mid])
node.left = self.sortedArrayToBST(nums[:mid])
node.right = self.sortedArrayToBST(nums[mid + 1:])
return node📌 51) 이진 탐색 트리(BST)를 더 큰 수 합계 트리로 ( 리트코드 1038. Binary Search Tree to Greater Sum Tree )
✔ 풀이 (In-Order로 노드 값 누적)
# 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:
val = 0
#중위순회 (오른쪽-부모-왼쪽)
def bstToGst(self, root: TreeNode) -> TreeNode:
if root:
self.bstToGst(root.right) #오른쪽 자식노드
self.val += root.val
root.val = self.val
self.bstToGst(root.left) #왼쪽 자식노드
return root📌 52) 이진 탐색 트리(BST) 합의 범위 ( 리트코드 938. Range Sum of BST )
✔ 풀이1 (재귀 구조 DFS로 브루트 포스 탐색)
# 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:
sum = 0
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root:
return 0
return (root.val if low <= root.val <= high else 0) + self.rangeSumBST(root.right, low, high) + self.rangeSumBST(root.left, low, high)📝 해당 풀이는 모든 노드를 탐색하는 브루트 포스 풀이임으로 최적화가 필요.
✔ 풀이2 (DFS 가지치기로 필요한 노드 탐색)
# 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 rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
def dfs(node):
if not node:
return 0
if node.val < low:
return dfs(node.right)
elif node.val > high:
return dfs(node.left)
else:
return node.val + dfs(node.left) + dfs(node.right)
return dfs(root)✔ 풀이3 (반복 구조 DFS로 필요한 노드 탐색)
# 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 rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
stack, sum = [root], 0
while stack:
node = stack.pop()
if node:
if node.val < low:
stack.append(node.right)
elif node.val > high:
stack.append(node.left)
else: #low <= node.val <= high:
sum += node.val
stack.append(node.right)
stack.append(node.left)
return sum✔ 풀이4 (반복 구조 BFS로 필요한 노드 탐색)
# 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 defaultdict
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
q, sum = deque([root]), 0
while q:
node = q.popleft()
if node:
if node.val < low:
q.append(node.right)
elif node.val >high:
q.append(node.left)
else:
sum += node.val
q.append(node.left)
q.append(node.right)
return sum📌 53) 이진 탐색 트리(BST) 노드 간 최소 거리 ( 리트코드 783. Minimum Distance Between BST Nodes )
✔ 풀이1 (재귀 구조로 중위 순회)
# 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:
prev = float('-inf') #이전에 방문한 노드의 값
distance = float('inf') #거리
#재귀 함수
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
if root:
if root.left: #왼쪽 자식 노드 방문
self.minDiffInBST(root.left)
self.distance = min(self.distance, root.val - self.prev)
self.prev = root.val
if root.right: #오른쪽 자식 노드 방문
self.minDiffInBST(root.right)
return self.distance✔ 풀이2 (반복 구조로 중위 순회)
# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
distance, prev = float('inf'), float('-inf')
stack, node = [], root
while stack or node:
while node: #왼쪽 노드를 stack에 추가
stack.append(node)
node = node.left
node = stack.pop()
distance = min(distance, node.val - prev)
prev = node.val
node = node.right #오른쪽 노드로 이동
return distance📌 이진 트리 순회 구현
# (1)
# / \
# (2) (3)
# / \
# (4) (5)
#Inorder (Left, Root, Right) 4 2 5 1 3
#Preorder (Root, Left, Right) 1 2 4 5 3
#Postorder (Left, Right, Root) 4 5 2 3 1
class Node:
def __init__(self, data):
self.val = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def setRoot(self, node): #root node 지정
self.root = node
def makeNode(self, left_node, data, right_node):
node = Node(data)
node.left = left_node
node.right = right_node
return node
def in_order(self, node):
if node:
self.in_order(node.left)
print(node.val, end = ' ')
self.in_order(node.right)
return
def pre_order(self, node):
if node:
print(node.val, end = ' ')
self.pre_order(node.left)
self.pre_order(node.right)
return
def post_order(self, node):
if node:
self.post_order(node.left)
self.post_order(node.right)
print(node.val, end = ' ')
return
if __name__ == '__main__':
bt = BinaryTree()
n4 = bt.makeNode(None, 4, None)
n5 = bt.makeNode(None, 5, None)
n2 = bt.makeNode(n4, 2, n5)
n3 = bt.makeNode(None, 3, None)
n1 = bt.makeNode(n2, 1, n3)
bt.setRoot(n1)
print('Inorder ', end = ' ')
bt.in_order(bt.root)
print('\nPreorder ', end = ' ')
bt.pre_order(bt.root)
print('\nPostorder ', end = '')
bt.post_order(bt.root)📌 54) 전위, 중위 순회 결과로 이진 트리 구축 ( 리트코드 105. Construct Binary Tree from Preorder and Inorder Traversal )
✔ 풀이 (전위 순회 결과로 중위 순회 분할 정복)
# 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 defaultdict
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
preorder = deque(preorder) #popleft사용하기 위해 deque사용
def div(preorder, inorder):
if inorder:
#preorder에서 분할 지점 구하기
idx = inorder.index(preorder.popleft())
#inorder에서 분할 지점을 기준으로 분할
node = TreeNode(inorder[idx])
node.left = div(preorder, inorder[:idx])
node.right = div(preorder, inorder[idx + 1:])
return node
return div(preorder, inorder)
📝 버그 난 코드
from collections import defaultdict
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if inorder:
preorder = deque(preorder)
#preorder에서 분할 지점 구하기
idx = inorder.index(preorder.popleft())
#inorder에서 분할 지점을 기준으로 분할
node = TreeNode(inorder[idx])
node.left = self.buildTree(preorder, inorder[:idx])
node.right = self.buildTree(preorder, inorder[idx + 1:])
return node👉 ValueError
deque를 사용하기 위해 다음과 같이 재귀함수 내에 preorder = deque(preorder) 처럼 재할당 하면 지역변수가 됨. 따라서 preorder의 값이 의도한 대로 전달되지 X
