计算布尔二叉树的值
难度:
标签:
题目描述
给你一棵 完整二叉树 的根，这棵树有以下特征：
- 叶子节点 要么值为
0要么值为1，其中0表示False，1表示True。 - 非叶子节点 要么值为
2要么值为3，其中2表示逻辑或OR，3表示逻辑与AND。
计算 一个节点的值方式如下：
- 如果节点是个叶子节点，那么节点的 值 为它本身，即
True或者False。 - 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
示例 1：
输入：root = [2,1,3,null,null,0,1] 输出：true 解释：上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。 根节点的值为 True ，所以我们返回 true 。
示例 2：
输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
提示：
- 树中节点数目在
[1, 1000]之间。 0 <= Node.val <= 3- 每个节点的孩子数为
0或2。 - 叶子节点的值为
0或1。 - 非叶子节点的值为
2或3。
代码结果
运行时间: 32 ms, 内存: 16.3 MB
/*
* 题目思路：
* 利用Java Stream API进行递归计算二叉树的布尔值。虽然Stream API并不适合树的结构，
* 但是通过递归调用方法来实现类似效果。叶子节点的值直接返回，
* 非叶子节点的值通过计算子节点值并根据运算符进行布尔运算。
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
import java.util.function.Supplier;
public class Solution {
public boolean evaluateTree(TreeNode root) {
Supplier<Boolean> compute = () -> {
if (root.left == null && root.right == null) {
return root.val == 1;
}
boolean leftValue = evaluateTree(root.left);
boolean rightValue = evaluateTree(root.right);
return root.val == 2 ? leftValue || rightValue : leftValue && rightValue;
};
return compute.get();
}
}
解释
方法:
题解通过递归的方式计算二叉树的布尔值。如果节点是叶子节点（即没有左子节点），它的值直接根据其节点值返回True或False（1对应True，0对应False）。如果节点是非叶子节点，根据节点值分别执行OR（值为2）和AND（值为3）操作。这样，通过递归地计算左右子树的布尔值，并根据当前节点的操作符合并这些值，最终得到树的根节点的布尔值。
时间复杂度:
O(n)
空间复杂度:
O(log(n))
代码细节讲解
🦆
在递归函数中，当判断一个节点是叶子节点时，你是如何确保这个节点没有任何子节点的？
▷🦆
对于非叶子节点的处理，你是如何确定这个节点要执行的是`OR`运算还是`AND`运算的？
▷🦆
题解中提到递归深度大约是log(n)，这是怎样计算得出的？完整二叉树的高度是否总是log(n)？
▷🦆
递归函数中如果遇到了val值既不是1也不是2也不是3的情况，应该如何处理？
▷