计算布尔二叉树的值-LeetCode

2331. 计算布尔二叉树的值 - Evaluate Boolean Binary Tree

🎯 问题描述（来源于LeetCode）

描述：
给你一棵完整二叉树的根节点 root，这棵树有以下性质：

• 叶子节点的值为 0 或 1，其中 0 表示 False，1 表示 True。
• 非叶子节点的值为 2 或 3，其中 2 表示逻辑或（OR），3 表示逻辑与（AND）。

计算该布尔二叉树的值，返回 True 或 False。

说明：

• 完整二叉树指每个非叶子节点都有两个子节点。
• 计算规则：对于非叶子节点，先递归计算左右子树的值，然后根据节点值应用对应的逻辑运算。

示例：

• 示例 1：

输入: root = [2,1,3,null,null,0,1]
输出: true
解释: 根节点值为2（OR），左叶子值为1 → true，右子树根值为3（AND），其左叶子0 → false，右叶子1 → true，AND结果 false，整体 OR(true, false) = true

• 示例 2：

输入: root = [0]
输出: false

💻 解题思路

思路1：递归后序遍历

算法步骤

1. 递归终止条件：

   • 如果当前节点是叶子节点（root.left is None and root.right is None），则返回布尔值 root.val == 1。

2. 递归计算左右子树：

   • 分别对左子树和右子树调用 evaluateTree，得到左右子树的布尔值。

3. 根据当前节点值进行逻辑运算：

   • 若 root.val == 2（OR），返回 左值 or 右值。
   • 若 root.val == 3（AND），返回 左值 and 右值。

4. 返回最终结果。

思路1：代码实现

# 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 is None:
            return False
        if root.val == 2:
            return self.evaluateTree(root.left) or self.evaluateTree(root.right)
        elif root.val == 3:
            return self.evaluateTree(root.left) and self.evaluateTree(root.right)
        elif root.left is None and root.right is None:
            return root.val == 1

思路1：📊 性能分析

复杂度验证

• 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。每个节点恰好被访问一次。
• 空间复杂度：$O(h)$，其中 $h$ 为树的高度。递归调用栈的深度等于树高，最坏情况（链状树）为 $O(n)$。

思考

• 本题是二叉树后序遍历的经典应用，计算逻辑表达式的值。
• 由于树是完整二叉树，无需额外判断空子节点，代码可以更简洁。
• 也可以使用迭代（栈）模拟后序遍历，但递归写法最直观。