You are given the root
of a full binary tree with the following properties:
- Leaf nodes have either the value
0
or1
, where0
representsFalse
and1
representsTrue
. - Non-leaf nodes have either the value
2
or3
, where2
represents the booleanOR
and3
represents the booleanAND
.
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
orFalse
. - 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
or2
children. - Leaf nodes have a value of
0
or1
. - Non-leaf nodes have a value of
2
or3
.
计算布尔二叉树的值。
给你一棵 完整二叉树 的根,这棵树有以下特征:
叶子节点 要么值为 0 要么值为 1 ,其中 0 表示 False ,1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ,其中 2 表示逻辑或 OR ,3 表示逻辑与 AND 。
计算 一个节点的值方式如下:如果节点是个叶子节点,那么节点的 值 为它本身,即 True 或者 False 。
否则,计算 两个孩子的节点值,然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/evaluate-boolean-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是递归。我直接给代码。
时间O(n)
空间O(n)
Java实现
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public boolean evaluateTree(TreeNode root) { 18 if (root.left == null) { 19 return root.val == 1; 20 } 21 if (root.val == 2) { 22 return evaluateTree(root.left) || evaluateTree(root.right); 23 } else { 24 return evaluateTree(root.left) && evaluateTree(root.right); 25 } 26 } 27 }
标签:node,2331,TreeNode,val,Binary,Evaluate,True,root,节点 From: https://www.cnblogs.com/cnoodle/p/17094324.html