【Leetcode每日一题】 递归 - 计算布尔二叉树的值（难度⭐⭐）（44）

1. 题目解析

题目链接：2331. 计算布尔二叉树的值

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

算法思路概述：

• 问题解释：我们面对的是一个节点可能含有逻辑运算符（AND，OR，XOR）的二叉树，节点值为0或1。
• 对于规模为n的问题，我们需要计算当前节点的值。
• 若当前节点值不是0或1，则将规模为n的问题拆分为规模为n-1的子问题：
  • 子节点的值；
  • 通过子节点的值进行运算得出当前节点的值。
• 当问题规模变为n=1时，即叶子节点，我们可以直接获取其节点值为0或1。

算法流程设计：

递归函数设计：

• 函数名：evaluateTree
• 返回值：当前节点值。
• 参数：当前节点指针。
• 功能：计算当前节点通过逻辑运算符得出的值。

递归函数流程：

1. 如果当前节点是叶子节点（即问题规模为n=1），直接返回当前节点值。
2. 递归计算左右子节点的值。
3. 根据当前节点的逻辑运算符，计算左右子节点值运算得出的结果。

解释：

• 通过递归函数evaluateTree，我们遍历二叉树节点，并根据逻辑运算符进行计算。
• 递归过程中，问题规模不断减小，直至叶子节点，然后逐级返回结果，最终得到整棵树的计算结果。

3.代码编写

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        if(root->left == nullptr) return root->val; 
        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);
        return root->val == 2 ? left | right : left & right;
    }
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~