[99클럽 코테 스터디] 2일차 TIL - 깊이/너비 우선 탐색(DFS/BFS), Evaluate Boolean Binary Tree

[2일차] 깊이/너비 우선 탐색(DFS/BFS)

 

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

* 대충 번역: full binary tree(모든 node의 child가 2개 or 0개인 트리)가 있다.

• 리프 node(자식이 없는 노드, 끝답)는 0 또는 1의 값을 가지고, 0은 False, 1은 True를 의미한다.
• 리프가 아닌 node들은 2 또는 3의 값을 가진다. 2는 OR을 의미하고, 3은 AND를 의미한다.
• 리프 노드의 평가는 해당 노드의 값이다. 즉 True 혹은 False이다.
• 리프 노드가 아니면, 노드의 boolean 연산을 노드의 두 자식에 적용한다.

root 노드를 평가하는 boolean 결과를 반환하라.

Solution

클래스에서 참조할 수 있는 값이 val, left, rigt이므로 재귀 호출을 통해 문제를 해결할 수 있다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def evaluateTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        
        if (root.left is None) or (root.right is None):
            return root.val

        if root.val == 2:
            result = self.evaluateTree(root.left) or self.evaluateTree(root.right)
        elif root.val == 3:
            result = self.evaluateTree(root.left) and self.evaluateTree(root.right)

        if result == 0:
            return False
        elif result == 1:
            return True

나다어

• full binary tree - 모든 node의 child가 2개 or 0개인 트리
• evaluation - 표현식 트리는 수학적 표현식을 트리 구조로 나타낸 것이고, 표현식 트리에서의 evaluation(평가)는 트리를 순회하며 수학적 표현식의 값을 계산하는 과정
• 반복 연산 즉 재귀를 사용해야 할 때는 복잡한 케이스를 커버하려고 하지 말고, 어디에서 함수를 호출해버리면 될지 고민하자.