力扣2331题：计算布尔二叉树的值 - 递归解法详解

内容简介

本文深入解析了力扣2331题"计算布尔二叉树的值"的递归解法。通过递归遍历布尔二叉树，根据节点类型(AND/OR)和叶子节点值计算整棵树的结果。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者理解树结构递归处理的技巧。

算法思路

1‌.递归终止条件‌：当节点为叶子节点时直接返回其布尔值

‌2.OR操作节点‌：值为2时递归计算左右子树的OR结果

‌3.AND操作节点‌：值为3时递归计算左右子树的AND结果

‌4.自底向上计算‌：从叶子节点开始向上传递计算结果

代码实现（带详细注释）

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        // 基本情况：如果是叶子节点，直接返回其布尔值(0或1)
        if (!root->left && !root->right) {
            return root->val;
        }
        
        // 如果当前节点是OR操作(值为2)
        if (root->val == 2) 
            // 递归计算左右子树的OR结果
            root->val = evaluateTree(root->left) || evaluateTree(root->right);
        else 
            // 否则是AND操作(值为3)，递归计算左右子树的AND结果
            root->val = evaluateTree(root->left) && evaluateTree(root->right);
            
        // 返回当前节点的计算结果
        return root->val;
    }
};

复杂度分析

‌时间复杂度‌：O(n)，需要访问树中的每个节点一次

‌空间复杂度‌：O(h)，递归栈空间取决于树的高度

优化方向

‌迭代解法‌：使用栈或队列实现非递归遍历

‌记忆化‌：对重复计算的子树结果进行缓存

‌并行计算‌：对左右子树可考虑并行处理

总结

布尔二叉树的求值问题展示了如何将逻辑运算与树结构递归完美结合。理解这种解法有助于掌握树问题的递归处理模式和布尔运算的应用场景。