2331. 计算布尔二叉树的值

🟢   🔖  树 深度优先搜索 二叉树  🔗 力扣 LeetCode

题目

You are given the root of a full binary tree with the following properties:

• Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
• Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

The evaluation of a node is as follows:

• If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
• Otherwise, evaluate the node's two children and apply the boolean operation of its value with the children's evaluations.

Return _the boolean result of evaluating the _root node.

A full binary tree is a binary tree where each node has either 0 or 2 children.

A leaf node is a node that has zero children.

Example 1:

Input: root = [2,1,3,null,null,0,1]

Output: true

Explanation: The above diagram illustrates the evaluation process.

The AND node evaluates to False AND True = False.

The OR node evaluates to True OR False = True.

The root node evaluates to True, so we return true.

Example 2:

Input: root = [0]

Output: false

Explanation: The root node is a leaf node and it evaluates to false, so we return false.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 3
• Every node has either 0 or 2 children.
• Leaf nodes have a value of 0 or 1.
• Non-leaf nodes have a value of 2 or 3.

题目大意

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

• 叶子节点 要么值为 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 。

解题思路

递归遍历树，从根节点开始，递归地评估左右子树的值。

• 如果当前节点值是 0，返回 false。
• 如果当前节点值是 1，返回 true。
• 如果当前节点值是 2，则返回左子树和右子树的逻辑“或”运算结果。
• 如果当前节点值是 3，则返回左子树和右子树的逻辑“与”运算结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的总数，每个节点都会被访问一次。
• 空间复杂度：O(n)，递归的深度为树的高度 h，最坏情况下空间复杂度为 O(h)，在树为链状时 h 为 n，因此空间复杂度为 O(n)。

代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var evaluateTree = function (root) {
	// 叶节点，0 表示 false
	if (root.val == 0) return false;

	// 叶节点，1 表示 true
	if (root.val == 1) return true;

	// 非叶节点，2 表示 OR 操作
	if (root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);

	// 非叶节点，3 表示 AND 操作
	if (root.val == 3) return evaluateTree(root.left) && evaluateTree(root.right);
};

相关题目

题号	标题	题解	标签	难度	力扣
1612	检查两棵二叉表达式树是否等价 🔒		树 深度优先搜索 哈希表 2+	🟠	🀄️ 🔗
1628	设计带解析函数的表达式树 🔒		栈 树 设计 3+	🟠	🀄️ 🔗
2313	二叉树中得到结果所需的最少翻转次数 🔒		树 深度优先搜索 动态规划 1+	🔴	🀄️ 🔗