【递归搜索回溯专栏】专题二：二叉树中的深搜----计算布尔二叉树的值

题目来源

本题来源为：

Leetcode 2331. 计算布尔二叉树的值

题目描述

给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。

非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算 一个节点的值方式如下：

如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。

否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。

返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

题目解析

我们举个例子：

题目说的是，2是逻辑或，3是逻辑与，0为false，1为true.

在根节点2那么他就是逻辑或，2的左节点为1，那么他就是true，2的右子树中：

3是逻辑与，要想将3节点的结果返回给根节点2，就需要知道3节点的左子树与右子树。3的左节点为0，那么就是false，右节点为1，那么就为true,取一个逻辑与，那么3节点的布尔值就为false.

现在看根节点2，左边是true，右边是false，取一个逻辑或，那么最后结果就是true,所以最后整棵树的布尔值就为true。

算法原理

把题目解析分析完，就很容易看出来相同的子问题：

要想知道根节点的布尔值，就需要知道根节点的左子树与右子树的布尔值。

计算左子树与右子树的布尔值的方法是一致的。

也可以近似理解为就相当与后序遍历一下这棵树。

函数头

函数头很简单，我们就传入根即可。

函数体

要想知道根的布尔，就需要知道根的左子树与右子树的值：

那么我们直接传入根的左子树与右子树（黑盒）我们相信这个黑盒一定能帮我们完成任务。

函数返回值

注意这颗二叉树是一颗完整二叉树：

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

因此我们首先判断根节点是否有左子树，其次根节点的值是否为0；

代码实现

class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        if(root->left==nullptr)
            return root->val==0?false:true;
        //递归
        bool left=evaluateTree(root->left);
        bool right=evaluateTree(root->right);
        return root->val==2?(left|right):(left&right);    
    }
};