2331. Evaluate Boolean Binary Tree

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

 

 

Difficulty : Easy

 

Status : Solved

 

Time : 00:04:22

 

---

 

문제 설명

 

 

---

 

풀이

 

DFS로 간단히 접근하자.

• 만약 현재 노드가 리프노드라면, 현재 노드값이 1인지의 boolean 값을 검사하여 반환하자.
• 리프노드가 아니라면, 조건상 Full binary tree이므로 왼쪽과 오른쪽 서브트리가 반드시 존재한다. 왼쪽, 오른쪽 결과물을 현재 노드값에 따라 or 연산, 혹은 and 연산을 가하여 바로 반환하면 된다.
• 비재귀로도 가능하겠지만 재귀면 역시 간단하게 풀린다.

 

풀이 코드(Python)

# Definition for a binary tree node.
# 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 root.val <= 1 :
            return root.val == 1
        left = self.evaluateTree(root.left)
        right = self.evaluateTree(root.right)
        if root.val == 2 :
            return left or right
        else :
            return left and right

 

 

풀이 코드(Go)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func evaluateTree(root *TreeNode) bool {
    switch root.Val {
        case 0 :
        case 1 :
        return root.Val == 1
        case 2 :
        return evaluateTree(root.Left) || evaluateTree(root.Right)
        case 3 :
        return evaluateTree(root.Left) && evaluateTree(root.Right)
    }
    return false
}