💬 Discord
Sign In
NeetCode #397LC-2331EasyTrees
← Back to All Problems

#397 · #2331 · Evaluate Boolean Binary Tree(计算布尔二叉树的值)

📌 Problem Statement & Constraints

You are given the root of a full binary tree where leaves have value 0 (false) or 1 (true), and internal nodes have value 2 (OR) or 3 (AND). Evaluate the tree and return the boolean result. Constraints: the number of nodes is in [1, 1000], 0 <= Node.val <= 3; every node has either 0 or 2 children.

💡 Core Algorithmic Approaches

  1. Recurse: leaves return their boolean value.
  2. An internal node with value 2 is OR, and with value 3 is AND.
  3. Combine the two children's results with the appropriate operator.
  4. The full-binary-tree guarantee means every internal node has exactly two children, so no arity checks are needed.

💻 Benchmark Python3 Implementation

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if not root.left and not root.right:
            return root.val == 1           # leaf
        if root.val == 2:                  # OR
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)
        return self.evaluateTree(root.left) and self.evaluateTree(root.right)   # AND

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping the OR and AND codes: 2 is OR and 3 is AND; getting this backwards inverts the result.
  • Checking root.val == 1 for internal nodes: internal nodes hold 2 or 3, never 0 or 1.
  • Assuming a node can have one child: the statement guarantees a full binary tree.
  • Returning the node value instead of a boolean: the API returns a boolean.