1. 오늘의 문제

Evaluate Boolean Binary Tree

• 출처 : leetcode

2. 문제 분석

• 완전 이진 트리의 루트 : root
• 완전 이진 트리의 규칙
  • Leaf 노드들은 0(False) 또는 1(True)이다.
  • Non-leaf 노드들은 2(OR) 또는 3(AND)이다.
• evaluation
  • Leaf 노드이면 True 또는 False 값을 가진다.
  • Leaf 노드가 아니면 두 개의 자식 노드를 가지고 자식 노드들의 연산을 실행
• 리턴 값 : root 노드의 결과값
• 완전 이진 트리는 자식이 아예 없거나 2개의 자식 가짐
• Leaf 노드는 자식을 가지지 않음
• 노드 개수는 1 이상 1,000 이하
• Node.val : 0 이상 3 이하
• 입출력 예시
  • Input : root = [2, 1, 3, null, null, 0, 1]
  • Output : true
  • Explanation : 0은 False이고 1은 True, Leaf 노드의 부모의 값은 3(AND)이므로 Leaf 노드의 부모의 값은 False가 됨. root 노드는 OR이며, 왼쪽 자식 노드는 Leaf 노드이므로 True, 오른쪽 자식 노드는 False가 된다. 즉, True OR False가 되니깐 리턴 값은 True가 됨

* Input : root = [0] * Output : false * Explanation : root 노드가 Leaf 노드임으로 0인 False 리턴

3. 문제 풀이

1. 재귀적으로 풀어야 함
2. return (root.left 부분 트리 연산) root.val (root.right 부분 트리 연산)

• 리턴값이 boolean 값이므로 연산을 나눠야함
• 만약 root.val = 2이면 (root.left 부분 트리 연산) OR (root.right 부분 트리 연산)
• 그렇지 않다면 (root.left 부분 트리 연산) AND (root.right 부분 트리 연산)

3. Leaf 트리는 0 또는 1 밖에 가지지 못함 ⇾ 0 또는 1이 아니면 자식이 있음.

• Leaf 트리의 자식이 null인 경우 false 리턴

4. Base Case: if (Leaf.val == 0 || Leaf.val == 1)이면 return Leaf.val

• 만약 leaf.val = 1이면 true, leaf.val = 0이면 false 리턴해서 연산 수행

4. 구현 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {
        // null 제외
        if (root == null) {
            return false;
        }

        // Base Case
        if (root.val == 1) {
            return true;
        }
        if (root.val == 0) {
            return false;
        }

        // 재귀
        if (root.val == 2) {
            return evaluateTree(root.left) || evaluateTree(root.right);
        }
        return evaluateTree(root.left) && evaluateTree(root.right);
    }
}

5. 오늘의 회고

• 점점 재귀호출 문제를 푸는 것에 익숙해진건지 어떻게 풀어야 할 지 좀 쉽게 생각나고 아이디어도 나온다.
• 그래서 그런지 오늘은 생각보다 되게 빨리 풀었다ㅎㅎ
• 행복한 하루가 될 것 같다!
  

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL