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를 반환
-> 트리를 재귀적으로 탐색하면서 각 노드의 값을 평가하여 최종 결과를 반환하였다.
'Algorithm > 릿코드' 카테고리의 다른 글
99클럽 코테 스터디 8일차 338. counting bits (0) | 2024.06.07 |
---|---|
99클럽 코테 스터디 7일차 1221. Split a String in Balanced Strings (0) | 2024.06.05 |
99클럽 코테 스터디 5일차 104. Maximum Depth of Binary Tree (1) | 2024.06.03 |
99클럽 코테 스터디 4일차 226. Invert Binary Tree (0) | 2024.06.03 |
99클럽 코테 스터디 2일차 TIL 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree (0) | 2024.05.31 |