[2024] day 61. Leetcode 1609. Even Odd Tree
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 2월 29일 (목)
Leetcode daily problem
1609. Even Odd Tree
https://leetcode.com/problems/even-odd-tree/description/?envType=daily-question&envId=2024-02-29
Problem
아래의 조건을 만족하는 트리를 Even Odd Tree 라고 하는데
(1) 이진 트리의 루트는 level 0에 있고, 루트의 자식노드는 level 1, 자식노드의 자식노드는 level 2에 있다.
(2) 모든 짝수 level에 대해 모든 노드는 왼쪽에서 오른쪽으로 증가하는 홀 수 값을 가진다.
(3) 모든 홀수 level에 대해 모든 노드는 왼쪽에서 오른쪽으로 감수하는 짝수 정수 값을 가진다.
이진 트리의 루트가 주어졌을 때 해당 트리가 'Even Odd Tree' 이면 True, 그렇지 않으면 False를 반환한다.
Solution
Tree, binary Tree, queue
BFS 알고리즘으로 각 이진 트리의 레벨 순서대로 노드를 방문해서,
해당 레벨의 짝/홀 수 유무에 따른 조건들이 맞는지 확인한다.
queue를 이용해 bfs를 구현하고 현재 레벨에 있는 모든 노드가 들어가고, 노드를 다 서칭하면 각 노드의 자식들이 큐에 들어가면서 각 레벨에 대한 순차처리를 가능하게 한다.
짝수 레벨에서는 노드의 값이 홀수여야하고, 왼쪽에 위치한 노드의 값이 오른쪽에 위치한 노드의 값보다 작아야 하는 조건이고
홀수 레벨에서는 노드의 값은 짝수여야 하며, 왼쪽에 위치한 노드의 값이 오른쪽에 위치한 노드의 값보다 커야 하는 조건이다.
각 노드를 움직이면서 이전 노드의 값을 업데이트 해주어야 하고
해당 조건에 따라 False, True를 주고 나머지 자식 노드가 존재하면 queue에 넣으면서 한 레벨이 끝나면 다음 레벨을 업데이트 한다.
Code
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
queue = deque([root])
level = 0
while queue:
prev_val = None
for _ in range(len(queue)):
node = queue.popleft()
if (level%2==0 and (node.val%2==0 or (prev_val is not None and node.val <=prev_val))) or \
(level%2!=0 and (node.val%2!=0 or (prev_val is not None and node.val >= prev_val))):
return False
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
prev_val = node.val
level +=1
return True
해당 코드에서 조건은
짝수레벨인 경우
(level % 2 == 0 and (node.val % 2 == 0 or (prev_val is not None and node.val <= prev_val))): 짝수 레벨인 경우를 처리한다.
- level % 2 == 0: 현재 레벨이 짝수인지 확인
- node.val % 2 == 0: 현재 노드의 값이 짝수인지 확인
- prev_val is not None and node.val <= prev_val: 이전 값이 존재하고, 현재 값이 이전 값보다 작거나 같은지 확인 한다.
(level % 2 != 0 and (node.val % 2 != 0 or (prev_val is not None and node.val >= prev_val))): 홀수 레벨인 경우를 처리한다.
- level % 2 != 0: 현재 레벨이 홀수인지 확인
- node.val % 2 != 0: 현재 노드의 값이 홀수인지 확인
- prev_val is not None and node.val >= prev_val: 이전 값이 존재하고, 현재 값이 이전 값보다 크거나 같은지 확인한다. 이 조건은 현재 값이 이전 값보다 크거나 같은 경우가 있으면 False를 반환한다.
Complexicity
시간 복잡도
해당 코드의 시간복잡도는 O(n) 인데, 여기서 n은 이진 트리의 노드의 수이다. 모든 노드를 한 번씩 방문해야하므로 이진트리의 모든 노드를 순회하는데 O(n)이 소요된다.
공간 복잡도
공간 복잡도는 O(n)이고, 여기서 n은 트리의 최대 너비이다.
너비 우선 탐색(BFS)를 사용하고 있어서 큐에는 한번에 한 레벨씩 노드가 들어간다. 큐에 가장 많은 노드 수만큼 메모리가 사용되므로, 트리의 너비에 비례하는 O(n)의 공간복잡도를 가진다.
위에서 업데이트하는 기존의 노드의 값을 None이 아닌
짝수일때는 임의로 작은 값 float('-inf') 홀수 일때는 임의로 큰 값 float('inf') 를 넣어주면 기존의 로직이었던, 이전 노드가 값이 존재하는지가 아니라 그냥 기존 노드의 값과 현재 노드의 값을 비교하는 로직으로 변경할 수 있다.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
queue = deque([root])
level = 0
while queue:
prev_val = float('-inf')if level%2==0 else float('inf')
for _ in range(len(queue)):
node = queue.popleft()
if (level%2==0 and (node.val%2==0 or node.val<=prev_val)) or (level%2!=0 and (node.val%2!=0 or node.val >=prev_val)):
return False
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
prev_val = node.val
level+=1
return True
