https://leetcode.com/problems/maximum-depth-of-binary-tree/
이진 트리의 최대 깊이
'''
트리 구조 또한 링크된 개별 요소를 찾아 따라가야 하기 때문에 재귀 함수와 친해보임
'''
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def make_tree_by(lst: List[int], idx: int) -> TreeNode:
parent = None
# index와 list의 길이를 비교해 아직 list에 참조 가능한 요소가 남아있는지 판별
if idx < len(lst):
value = lst[idx]
# value가 None이면 참조 가능했던 마지막 요소라는 뜻 임으로 리턴
if value is None:
return
# 현재 값을 부모 요소에 넣음
parent = TreeNode(value)
# 재귀 함수를 통해 left와 right에 각각 요소를 넣어줌
parent.left = make_tree_by(lst, 2 * idx + 1)
parent.right = make_tree_by(lst, 2 * idx + 2)
# parent가 리턴되면서 초기 호출한 곳에서는 루트를 리턴 받고
# 하위 요소들은 left, right 등에 할당 됨
return parent
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
tree = make_tree_by(root,0)
if not tree:
return 0
queue = deque([tree])
depth = 0
# 큐에 요소가 존재하다면 진행
while queue:
# 깊이를 1 증가 시킴
depth +=1
# 큐에 존재하는 만큼 반복 진행
for _ in range(len(queue)):
# 현재 큐에서 왼쪽부터 값을 꺼냄
cur = queue.popleft()
# 해당 요소에 왼쪽 요소나 오른쪽 요소가 있다면 새롭게 큐에 넣음
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
# 초기에 존재하는 요소만큼 반복이 진행됨
# 즉 레벨 1 만큼의 요소가 처리되고 나면, 큐에 남아있는 것은 새롭게 추가된 레벨 2의 요소들
# 레벨 만큼 반복 처리되면서 증가된 깊이를 반환
return depth
https://programmers.co.kr/learn/courses/30/lessons/12985
예상 대진표
'''
초기 생각
일단 트리 구조를 역순으로 따라 올라가는 구조
구해야 하는 건 두 노드가 만나는 지점...
본인의 상위 트리로 넘어가면 새로운 번호를 받는데 이 수식은 N/2
즉 한 단계가 끝날 때 마다 현재 값에서 나누기 2가 진행 됨
홀수인 경우에는 + 1을 하고 나눠줘야함
'''
'''
개인 답안: 어차피 단계가 올라갈 때 마다 n/2 되는 것에 착안함
라운드 수n은 2의 n승이기 때문에 늘 짝수, 1 이하가 될때까지 진행하고도 결과가 안나온다면 어차피 마지막 라운드기 때문에 바로 리턴
라운드가 진행 할 때마다 n은 절반씩 떨어짐
라운드가 진행되고 나면 a와 b를 비교함
만약 처음 라운트부터 만난 경우라고 해도 첫 루틴에서 한번 돌고 1이 된 a와 b를 비교하면 첫 라운트부터 싸웠다는 것을 알게됨
테스트 결과는 잘 해결됨
1,2 - 3,4 - 5,6
'''
def solution(n,a,b):
answer = 0
while n>=2:
n /= 2
if a == b:
print(answer)
return answer
a = int(a/2) + a%2
b = int(b/2) + b%2
answer += 1
return answer
'''
답안 1 숏코드
선수의 위치 a와 b 값을 2비트 수로 표현시 b가 인접한 위치로 가려면 두 비트가 같을 때는 0을 더하고 두 비트가 다를 때는 1을 더하는 XOR 연산 이라는데 이해는 안감
8, 4, 7를 예시로 진행
a-1 = 4-1 = 3 = 00000011
b-1 = 7-1 = 6 = 00000110
(a-1)^(b-1) = 00000011 ^ 00000110 = 00000101 = 5
.bit_length()는 대상의 정수를 표현하기 위한 비트의 수를 반환
5는 101 즉 3개의 비트 사용
5.bit_length() = 3
전개는 이해 되는데, 왜 그런지는 이해가 안됨
'''
def solution(n,a,b):
return ((a-1)^(b-1)).bit_length()
'''
답안 2
a와 b가 같아질 때 까지 count를 올림
난 %를 사용해 나눈 나머지의 값을 더했음
여기선 슬래시를 2개 사용해
나머지 연산에서 나눈 몫을 가져옴
같으면서도 스타일리쉬 함
홀수의 경우를 위해 +1를 진행
a, b
'''
def solution(n,a,b):
answer = 0
while a != b:
answer += 1
a, b = (a+1)//2, (b+1)//2
return answer
'''
답안 3
그냥 무조건 정답 처리하는 코드
지금은 막힘
어디서 야바위질이여
'''
class ALWAYS_CORRECT(object):
def __eq__(self,other):
return True
def solution(n,a,b):
answer = ALWAYS_CORRECT()
return answer;https://leetcode.com/problems/diameter-of-binary-tree/
이진 트리의 직경
초기생각
방안 1: 노드 1부터 시작해서 하위로 계속 뻣어나가 마지막 요소끼리를 찾고 그 간격을 더한다.
방안 2: 가장 마지막 노드부터(리스트에 마지막 요소) 시작해 끝을 찾아 나간다.
방안 3: 입력 값은 숫자의 범위다. 즉 수식이 존재함
리스트의 마지막 요소는 가장 깊은 값,
깊이는 한단계씩 상위 요소로 진행 할 때마다 1씩 늘어남
최상위에서는 다시 하위로 내려가며, 진행 할 때마다 1씩 늘어남
즉 상위요소올라갈 때 마다 2씩 증가한다고 가정하고 동작 가능...
하지만 마지막 요소와 반대편의 요소가 깊이가 다른 경우도 고려해야함
1
2 3
4 5 6 7
89 1011 1213 1415
1617 ...
17부터 시작한다고 가정
17-8-4-2-1-3-7-15
7의 지름을 가지며, 1에 도달시 4을 보유
반대편의 최대 깊이에 따라서 4*2를 한 8에서 -1을 할지 결정해야함
일단 노드는 2의 n 승으로 결정 됨
반대편을 구분하는 기준은 2^n + 2^(n-1) 승으로 구할 수있음
마지막 수를 기준으로 하기 때문에
2^n + 2^(n-1) 값이 마지막 수보다 작은 경우라면
마지막 수는 이미 중앙 점을 넘은 상태,
즉 반대편에는 같은 값이 있음으로 1에 도달 시 *2가 성립
없는 경우에는 *2한 값에 -1 해주면 됨
'''
from collections import deque
from typing import Optional
'''
개인답안
아 이거 백준 아니었음....
TreeNode 활용해야함...야발
'''
# 폐기
'''
list = input()
n = 0
length = 0
target = int(list[-1])
while target>1:
target = target//2
n += 1
if 2 ** n + 2**(n-1) < int(list[-1]):
n = n*2
else:
n = n*2 -1
print(n)
'''
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
'''
개인답안
이것저것 처리하면서
[1, 2, 3, 4, 5]
[1, 2]
[1]
등 다 통과했는데
[2,3,null,1] 이런게 나옴 야발
이건 뭐여 도데체
너무 오랜 시간이 투자되서 여기까지 하고 포기
'''
def diameterOfBinaryTreeMyway(self, root: Optional[TreeNode]) -> int:
length = -1
queue = deque([root])
target = None
if not root or root.left is None and root.right is None :
return 0
while queue:
length +=1
for _ in range(len(queue)):
target = queue.popleft()
if target.left:
queue.append(target.left)
if target.right:
queue.append(target.right)
print(f'length:{length}')
print(f'target.val:{target.val}')
if 2 ** length + 2**(length-1) < int(target.val):
length = length*2
else:
length = length*2 -1
return length
'''
답안
dfs 방식으로 탐색하면서 품,
가장 긴 탐색값을 계속 max로 이어 붙임
오른쪽과 왼쪽 깊이는 다시 def 연산을 통한 결과 값을 가져와 넣어줌
테스트 케이스가 [1, 2, 3, 4, 5]인 경우
longest:0, left:-1, right:-1, left+right+2: 0, return:0
longest:0, left:-1, right:-1, left+right+2: 0, return:0
longest:0, left:0, right:0, left+right+2: 2, return:1
longest:2, left:-1, right:-1, left+right+2: 0, return:0
longest:2, left:1, right:0, left+right+2: 3, , return 필요없음(더이상 계산 안함)
dfs이기 때문에 가장 깊은 5부터 연산을 한 결과 하위 노드가 없으니 0을 리턴
이후에 올라가서 4와 5의 상위 구조인 3부터
2은 하위에 노드가 존재하니 0+0+2의 결과를 반환,
이후 해당 반환값을 유지
3번은 하위 값이 없기 때문에 결과값 0 최대값 2는 유지됨
1번 최 상단에 와서부터 변화가 생김
3번은 노드가 없기에 -1+1 리턴으로 0이 반환 됨
2번은 노드가 존재해 0+1 = 1 이 반환됨
1번 노드에서 left는 1이 담김(2번 노드)
기존 최대 값 2과 left+right+2 = 1+0+2 = 3 비교해 더 높은 3이 담김
이후 모든 처리가 끝나고 최대값을 반환
left와 right는 숫자를 계승하는 구조임
양쪽을 비교해 자신의 값을 쌓고, 그 값은 상위 노드에서 왼쪽과 오른쪽 깊이를 판별하는 지표가 됨
max(left,right)+1를 통해 결국 더 깊은 쪽의 값이 담기는 구조
그래서 깊이에 오른쪽 왼쪽 구분이 없음
그저 양쪽으로 가장 깊은 값을 가져옴
'''
longest: int = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(node: TreeNode)->int:
if not node:
return -1
left = dfs(node.left)
right = dfs(node.right)
print(f'longest:{self.longest}, left:{left}, right:{right}, left+right+2: {left+right+2}')
self.longest = max(self.longest, left+right+2)
return max(left,right)+1
dfs(root)
return self.longesthttps://leetcode.com/problems/longest-univalue-path/
가장 긴 동일 값의 경로
'''
초기 생각
일단 받은 노드는 준비되어있으니 규칙을 준비해야함
dfs 방식을 사용해 자신과 같은 값의 노드가 있는 경우 더해주는 방식을 취하면 될 듯 함
'''
from typing import Optional
'''
일단 받은 노드는 준비되어있으니 규칙을 준비해야함
dfs의 실제 처리는 말단에 상단 노드 부터
(말단은 거의 하는게 없이 확인 후 넘어감)
이전 소스코드를 통해 상단으로 올라가면서 처리하는 부분은 됨
다만 left에서 right로 넘어갈 때 처리가 안됨
하위에서 올라오는 데이터는 left, right 중 높은 값이 되어야함
다만 최대 값은 중간에서 left와 right를 다 검증해야함
'''
# 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:
'''
개인 답안
[5,4,5,1,1,5]
[1,4,5,4,4,5]
이런 케이스는 통과 했는데 좀 기다란 케이스를 통과 못함
이상하게 결과값이 높아서 보니깐 내가 초기화를 안했음
left = 0, right = 0 넣어주니 됨
'''
longest: int = 0
def longestUnivaluePathMyway(self, root: Optional[TreeNode]) -> int:
def dfs(node: TreeNode) -> int:
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
mid = 0
if node.left and node.val == node.left.val:
left += 1
else:
left = 0
if node.right and node.val == node.right.val:
right += 1
else:
right = 0
if node.left and node.right and node.val == node.right.val == node.left.val:
mid = left+right
self.longest = max(self.longest, left, right, mid)
return max(left, right)
dfs(root)
return self.longest
'''
답안
나와 비슷함, 아마도 이전 문제에 답지를 가져와 연장선으로 바꿔서 그런듯 함
mid 대신 left와 right를 합쳤는데
생각해보니 내 답안에서 mid를 따로 뺄 필요가 없음
0으로 처리하면 어차피 같지 않으면 더하는게 의미가 없으니
'''
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.resulthttps://leetcode.com/problems/invert-binary-tree/
이진 트리 반전
'''
초기 생각
보기에는 쉬워 보임...
dfs로 서로 left right 교환해주면 되나 싶음
'''
# Definition for a binary tree node.
import collections
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
from typing import Optional
'''
보기에 쉬운 만큼 쉬웠음
그냥 바꾸니 해결이 됨
'''
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(node: TreeNode)->int:
if not node:
return
dfs(node.left)
dfs(node.right)
node.left, node.right = node.right, node.left
return
dfs(root)
return root
'''
답안
Approach 1: Recursive
This is a classic tree problem that is best-suited for a recursive approach.
Algorithm
The inverse of an empty tree is the empty tree.
The inverse of a tree with root rr, and subtrees
\text{right}right and \text{left}left, is a tree with root rr,
whose right subtree is the inverse of \text{left}left,
and whose left subtree is the inverse of \text{right}right.
쉬운 만큼 dfs를 따로 할 필요가 없었음
그냥 호출하면 되는걸...
'''
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root
'''
답안 2
좀더 복잡한 예제인듯 함
재귀로 부르냐, Queue로 담느냐 차이...
'''
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
DFS, BFS, 백트래킹과 같은 탐색이 끝나고
좀더 단순한 자료구조인 트리가 나오니 오늘은 문제가 나름 풀렸음
쉬운만큼 집중이 잘 되고, 몇몇 문제는 쉽다고 느껴진 만큼 성장한게 있던것 같음
하지만 아무래도...난이도 조절은 필요한거 같음
갑자기 어려운 문제를 만나면 의지부터 꺽임...
달콤살벌