문제의 요지와 Skleton code는 아래와 같다.
"""
1. binary tree height 구하라
2. binary tree balanced 맞는지 체크
3. binary search tree 맞는지 체크
4. 두 노드의 common ancestor 모두 구하기
5. 두 노드의 lowest common ancestor 구하기
"""
일단 문제에 쓰인 저 단어들이 각 무엇을 뜻하는지 부터 체크해보기
1. height(T0)
트리의 높이 구하기:
- 정의: 트리의 높이는 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이입니다.
- 계산:
- 루트 8의 왼쪽 서브트리의 높이 = 2
- 루트 8의 오른쪽 서브트리의 높이 = 2
- 따라서 전체 높이는 3.
2. is_balanced(T0)
트리가 균형 잡혔는지 여부:
- 정의: 이진 트리가 균형 잡혔다는 것은 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하임을 의미합니다.
- 확인:
- 루트 노드 8의 왼쪽 높이 = 2, 오른쪽 높이 = 2 → 차이 = 0 (OK)
- 모든 서브트리에서도 이 조건이 유지됨.
출력:
graphql
코드 복사
True
3. is_bst(T0)
이진 탐색 트리(BST) 여부:
- 정의: 이진 탐색 트리는 모든 노드에 대해 왼쪽 자식 < 부모 < 오른쪽 자식이 성립해야 합니다.
- 확인:
- 모든 노드에서 조건이 성립됩니다.
예:- 3의 왼쪽 1 < 3 < 6
- 15의 왼쪽 11 < 15 < 20
- 모든 노드에서 조건이 성립됩니다.
4. common_ancestors(T0, T4, T7)
두 노드의 모든 공통 조상 찾기:
- 입력: T4 = 6, T7 = 4
- 공통 조상:
- 6과 4의 공통 조상은 3 → 8입니다.
5. lca(T0, T4, T7)
두 노드의 가장 낮은 공통 조상(LCA) 찾기:
- 입력: T4 = 6, T7 = 4
- LCA:
- 6은 4의 부모 노드이므로 가장 낮은 공통 조상은 6입니다.
이렇다고 한다. 얼핏봐도 1~3번은 좀 쉬워보이고 4,5번이 조금 짜쳐보인다.
그리고 앞에서 구한 코드를 뒤에서도 연계해서 사용할 수 있는 문제로 보여진다.
내가 구현한 코드는 아래와 같다.
조금 노가다성이 있는데, 스스로 만들어 본 몇몇 TEST CASE에 대해선 잘 통과하였다.
Edge case 검토를 엄청 빡빡하게 하진 않아서 Error가 좀 있을 순 있다.
class TNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(T: TNode) -> int:
# Edge case 생각하기
if not T : return 0
from collections import deque
q = deque([T])
ans = -1
while q:
n = len(q)
for i in range(n):
curr = q.popleft()
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
ans+=1
return ans
def is_balanced(T: TNode) -> bool:
from collections import deque
q = deque([T])
while q:
n = len(q)
for i in range(n):
curr = q.popleft()
cnt_left,cnt_right = 0,0
if curr.left:
q.append(curr.left)
cnt_left = height(curr.left)
if curr.right:
q.append(curr.right)
cnt_right = height(curr.right)
if abs(cnt_left - cnt_right) > 1:
return False
return True
def is_bst(T: TNode) -> bool:
if not T : return True
from collections import deque
s = deque([T])
while s :
n = len(s)
curr = s.pop()
if curr.left:
s.append(curr.left)
if curr.left.val > curr.val:
return False
if curr.right:
s.append(curr.right)
if curr.right.val < curr.val:
return False
return True
# 쪼매 어려운 파트
def common_ancestors(T: TNode, U: TNode, V: TNode) -> list[int]:
# Node Class를 건들 수가 없다면, dict를 이용해 Node별 parent를 쭉 저장해야 할듯
# 그리고 Node U, V 사이에 겹쳐지는 parent 구해서 반환
ans = []
dic = {T : []}
from collections import deque
q = deque([T])
while q:
curr = q.pop()
if curr.left :
dic[curr.left] = dic[curr] + [curr]
q.append(curr.left)
if curr.right :
dic[curr.right] = dic[curr] + [curr]
q.append(curr.right)
s1 = set()
s2 = set()
for x in dic[U]:
s1.add(x.val)
for x in dic[V]:
s2.add(x.val)
s3 = s1.intersection(s2)
return list(s3)
# 쪼매 어려운 파트
def lca(T: TNode, U: TNode, V: TNode) -> int:
# 위에 코드를 참조해서 각 Node 별로 parent를 순서대로(new update를 index 0으로) 추가한다음 마지막에 각자 자신을 index 0에다가 insert하고 서로의 ancestor list를 비교해가며 가장 낮은 index 공통분모를 찾는다.
# Node Class를 건들 수가 없다면, dict를 이용해 Node별 parent를 쭉 저장해야 할듯
# 그리고 Node U, V 사이에 겹쳐지는 parent 구해서 반환
ans = []
dic = {T.val : []}
from collections import deque
q = deque([T])
while q:
curr = q.pop()
if curr.left :
dic[curr.left.val] = [curr.val] + dic[curr.val]
q.append(curr.left)
if curr.right :
dic[curr.right.val] = [curr.val] + dic[curr.val]
q.append(curr.right)
lst1 = [U.val] + dic[U.val]
lst2 = [V.val] + dic[V.val]
for x in lst1:
for y in lst2:
if x==y : return x
# Test Case
if __name__ == "__main__":
T7, T8, T9 = TNode(4), TNode(9), TNode(13)
T3, T4 = TNode(1), TNode(6, T7, None)
T5, T6 = TNode(11, T8, T9), TNode(20)
T1, T2 = TNode(3, T3, T4), TNode(15, T5, T6)
T0 = TNode(8, T1, T2)
# print(height(T0)) # 3
# print(height(None)) # 3
# print(height(T8)) # 0
# print(height(T1)) # 2
# T15=TNode(5)
# T11=TNode(1,T15,None)
# T12=TNode(2,T11,None)
# T14=TNode(3)
# T13=TNode(4,T12,T14)
# print(is_balanced(T0)) # True
# print(is_balanced(T13)) # False
# print(is_balanced(T9)) # True
# T15=TNode(77)
# T11=TNode(1,T15,None)
# T12=TNode(3,T11,None)
# T14=TNode(6)
# T13=TNode(5,T12,T14)
# print(is_bst(T0)) # True
# print(is_bst(T13)) # False
# print(common_ancestors(T0, T4, T7)) # [3,8]
# print(common_ancestors(T0, T6, T9)) # [15,8]
# print(common_ancestors(T0, T1, T1)) # [8]
# print(common_ancestors(T0, T1, T3)) # [8]
print(lca(T0, T4, T7)) # 6
print(lca(T0, T2, T1)) # 8
print(lca(T0, T9, T2)) # 15
이 코드를 기준으로, GPT한테 평가를 좀 해달라고 했다.
논리적으로 이상하거나 효율화시킬 수 있는 부분을 알려달라고 했다는!
전반적으로 주어진 코드는 주어진 이진 트리 문제를 매우 잘 해결했으며, 트리 순회와 데이터 저장 방식을 잘 사용했습니다. 다만 몇 가지 개선 사항과 평가를 제시하겠습니다.좋은 점
개선 사항
평가 요약장점:
개선점:
개선된 코드 요약최적화된 코드의 각 부분은 위에 제시한 재귀적 DFS를 활용하며 시간 복잡도도 개선되었습니다.전체적으로 개선하면 코드가 O(N) 시간 복잡도로 작동하며, 구조가 더 명확해집니다. 학습 포인트:
|
개인적으로 height 부분은 넘 깔끔하게 recursion으로 떨어져서 적용할만하고,
is_balanced랑 is_bst는 저기까지 코드 최적화하는 방법을 자연스리 생각해낼 수 있으려나 싶다 ㅎㅎ;;
- E. O. D -