99클럽 코테 스터디 4일차 TIL + 이진 검색 트리(3)

 

오늘의 공부 키워드

• 이진검색 트리(BST) 새로운 문제
• 2331 Evaluate Boolean Binary Tree

LeetCode 2331 Evaluate Boolean Binary Tree

문제 설명

주어진 문제는 이진 트리를 평가하여 그 결과를 반환하는 것입니다. 이진 트리는 다음과 같은 특징을 가지고 있습니다:

1. 리프 노드 (Leaf nodes): 자식이 없는 노드로 값이 0 또는 1입니다. 여기서 0은 False(거짓), 1은 True(참)을 나타냅니다.
2. 비 리프 노드 (Non-leaf nodes): 자식이 있는 노드로 값이 2 또는 3입니다. 2는 논리 OR 연산을 나타내고, 3은 논리 AND 연산을 나타냅니다.

이진 트리 평가는 다음과 같이 이루어집니다:

• 리프 노드의 경우, 그 값이 평가 결과가 됩니다.
• 비 리프 노드의 경우, 두 자식 노드를 평가하고, 그 결과에 대해 해당 노드의 논리 연산(OR 또는 AND)을 적용합니다.

 

문제 해결

이 문제를 해결하기 위해서는 주어진 이진 트리를 재귀적으로 평가하는 방법을 사용합니다. 트리를 탐색하면서 각 노드를 평가하고, 그 결과를 반환합니다.

 

코드

 

# TreeNode 클래스를 정의합니다.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def evaluateTree(root):
    # 리프 노드일 경우, 그 값을 반환합니다.
    if root.left is None and root.right is None:
        return root.val == 1
    
    # 좌측과 우측 자식을 재귀적으로 평가합니다.
    left_val = evaluateTree(root.left)
    right_val = evaluateTree(root.right)
    
    # 비 리프 노드일 경우, 해당 연산을 수행합니다.
    if root.val == 2:  # OR 연산
        return left_val or right_val
    elif root.val == 3:  # AND 연산
        return left_val and right_val

# 예제 1
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3, TreeNode(0), TreeNode(1))
print(evaluateTree(root1))  # 출력: True

# 예제 2
root2 = TreeNode(0)
print(evaluateTree(root2))  # 출력: False

 

코드 설명

1. TreeNode 클래스: 이진 트리의 노드를 정의하는 클래스입니다.
2. evaluateTree 함수: 트리를 재귀적으로 평가하는 함수입니다. 리프 노드인지 확인하고, 비 리프 노드일 경우 좌우 자식을 재귀적으로 평가하여 논리 연산을 수행합니다.
3. 예제 실행: 두 예제를 통해 함수를 테스트하고 결과를 출력합니다.

이 코드를 통해 주어진 이진 트리를 평가하여 그 결과를 반환할 수 있습니다.

 

오늘의 회고

• 이진 검색 트리를 다르게 푸는 방법을 알수 있어서 좋았다.
• 이진 검색 트리 새로운 문제가 많다는걸 다시한번 느껴서 도전 정신이 느껴진다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보려는 이유 및
    어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 바로바로 문제를 풀지 못하는점은 아직도 아쉽다
• chat gpt로 코딩테스트 연습하는거도 좋다고 생각한다..