[LeetCode] 2331. Evaluate Boolean Binary Tree

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

leetcode - Evaluate Boolean Binary Tree

문제 유형 : 이진트리, dfs, 재귀

문제 난이도 : Easy

 

문제

You are given the root of a full binary tree with the following properties:

• Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
• Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

The evaluation of a node is as follows:

• If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
• Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

Return the boolean result of evaluating the root node.

A full binary tree is a binary tree where each node has either 0 or 2 children.

A leaf node is a node that has zero children.

 

완전 이진 트리의 루트가 주어진다.

리프노드는 0, 1의 값을 가지는데, 각각 false와 true이다.

리프노드가 아닌 노드는 2,3의 값을 가지는데, 각각 or과 and를 의미한다

 

노드를 단순히 왼쪽에서 오른쪽으로 읽을 때의 수식을 기준으로 계산 결과를 구하시오.

 

풀이

쉽게 후위 순회를 통해서 풀 수 있다.

현재 노드가 만약 0과 1이라면, 리프 노드이므로 대응되는 논리값을 반환하면 되고, 

아니라면, 자식 노드의 논리값을 호출하여 논리연산값을 반환한다.

 

완전 이진 트리이므로, 리프노드가 아닌 경우 자식 노드가 반드시 2개이니 널 포인터 접근은 걱정할 것 없다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root -> val -2 < 0) {
            return root -> val;
        }

        bool left = evaluateTree(root -> left);
        bool right = evaluateTree(root -> right);
        if(root -> val == 2) {
            return left || right;
        }
        return left && right;
    }
};