99클럽 코테 스터디 12일차 TIL + 완전 이진 트리, DFS, [leetcode] Evaluate Boolean Binary Tree

✨ 문제 

Evaluate Boolean Binary Tree

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: 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.

 

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

 

 

 

✨ 개념

완전 이진 트리

- 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있음.

- 왼쪽에서 오른쪽으로 채워짐.

- 마지막 레벨에는 노드들이 가능한 한 왼쪽으로 몰려있음.

 

포화 이진 트리와 완전 이진 트리의 차이점

- 포화 이진 트리 : 모든 노드가 0개 또는 2개의 자식을 가지며, 모든 레벨이 완전히 채워져있음.

- 완전 이진 트리 : 모든 레벨이 완전히 채워져 있지만, 마지막 레벨은 왼쪽부터 차례로 채워짐.

 

 

 

✨ 최종코드

public boolean evaluateTree(TreeNode root) {
    if (root == null)
        return false;

    if (root.left == null && root.right == null)
        return root.val == 1;

    boolean leftValue = evaluateTree(root.left);
    boolean rightValue = evaluateTree(root.right);

    if (root.val == 2) // OR 연산
        return leftValue || rightValue;
    else if (root.val == 3) // AND 연산
        return leftValue && rightValue;

	return false;
}