99클럽 코테 스터디 3일차 2331. Evaluate Boolean Binary Tree

 

 

https://leetcode.com/problems/evaluate-boolean-binary-tree/description/

 

주어진 불리언 이진 트리의 루트 노드가 주어집니다. 각 노드는 0 또는 1의 값을 가지며, 리프 노드가 아닌 경우 논리 연산자 OR(2) 또는 AND(3)을 나타냅니다.

트리를 평가하여 그 결과를 반환하세요.

예제 1:

입력: root = [2,1,3,null,null,0,1] 출력: true 설명: 루트 노드가 OR(2) 연산자이고, 왼쪽 자식이 1, 오른쪽 자식이 AND(3) 연산자입니다. AND(3) 연산자의 왼쪽 자식이 0, 오른쪽 자식이 1입니다. 따라서 결과는 true입니다.

예제 2:

입력: root = [0] 출력: false 설명: 루트 노드가 0이므로 결과는 false입니다.

제약 조건:

• 트리의 노드 수는 [1, 1000] 범위 내에 있습니다.
• 노드의 값은 0, 1, 2, 또는 3입니다.

 

풀이

 

주어진 트리에서 리프 노드는 0 또는 1의 값을 가지며, 리프 노드가 아닌 노드는 2(OR) 또는 3(AND) 연산자를 나타낸다.

트리를 재귀적으로 탐색하면서 각 노드를 평가해야한다

 

# 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 evaluateTree(self, root: Optional[TreeNode]) -> bool:
        # 리프 노드인 경우 해당 값을 반환
        if not root.left and not root.right:
            return root.val == 1

        # 왼쪽과 오른쪽 자식 노드를 재귀적으로 평가
        left_val = self.evaluateTree(root.left)
        right_val = self.evaluateTree(root.right)

        # 현재 노드가 OR 연산자인 경우
        if root.val == 2:
            return left_val or right_val
        
        # 현재 노드가 AND 연산자인 경우
        if root.val == 3:
            return left_val and right_val

        # 기본적으로 False 반환 (논리적 오류 방지)
        return False

 

 

evaluateTree 구현 방법

 

리프 노드인 경우: root 노드의 left와 right가 없으면 리프 노드이다. root.val이 1이면 True를, 0이면 False를 반환

재귀 호출: 왼쪽과 오른쪽 자식 노드를 재귀적으로 평가하여 left_val과 right_val에 저장

OR 연산자: root.val이 2인 경우, left_val 또는 right_val 중 하나라도 True이면 True를 반환

AND 연산자: root.val이 3인 경우, left_val과 right_val 모두 True일 때만 True를 반환

 

-> 트리를 재귀적으로 탐색하면서 각 노드의 값을 평가하여 최종 결과를 반환하였다.