[2024] day 138. Leetcode 2331. Evaluate Boolean Binary Tree

gunny·2024년 5월 15일

leetcode 2331. Evaluate Boolean Binary Tree leetcode 2331. Evaluate Boolean Binary Tree python

코딩테스트

목록 보기

452/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 16일 (목)
Leetcode daily problem

2331. Evaluate Boolean Binary Tree

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

Problem

다음 속성을 가진 이진 트리가 있다.
리프 노드의 값은 0 또는 1인데, 여기서 0은 False를 나타내고 1은 True를 나타낸다.리프가 아닌 노드의 값은 2 또는 3이다. 여기서 2는 boolean OR을 나타내고 3은 boolean AND를 나타낸다.

노드가 리프 노드인 경우 evalutation은 노드의 값, 즉 True 또는 False이다. 그렇지 않으면 노드의 두 자식을 평가하고 해당 값의 boolean 연산을 자식 노드 evaluation에 적용합니다.
루트 노드를 평가한 boolean 결과를 반환한다.

완전 이진 트리는 각 노드가 0개 또는 2개의 자식을 갖는 이진 트리이다.
리프 노드는 자식이 없는 노드이다.

Solution

DFS, recursive

해당 문제는 dfs 재귀 호출을 이용해서 트리를 순회하면서 각 노드를 평가한다.

기본 케이스로 root 에 left, right 자식노드가 없면 리프토드 이므로 리프 노드의 값이 0이면 False, 1이면 True를 반환한다.

그 이후로 리프 노드가 아닌 경우 왼쪽 서브트리와 오른쪽 서브트리 평가하기 위해 해당 함수를 재귀적으로 호출한다.
그래서 현재 노드의 값이 2이면 OR 연산, 노드의 값이 3이면 AND 연산을 수행하고 결과를 반환한다.

Code

# 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
        
        sub_tree_left = self.evaluateTree(root.left)
        sub_tree_right = self.evaluateTree(root.right)
        
        if root.val == 2:
            evaluate_root = sub_tree_left or sub_tree_right
            
        else:
            evaluate_root = sub_tree_left and sub_tree_right
            
        
        return evaluate_root