计算布尔二叉树的值【LC2331】
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.
吃饱饱喝饱饱学习习
- 思路：DFS
使用深度搜索，返回每颗子树的布尔值，每颗子树的布尔结果与其布尔操作有关，即父节点的值，因此递归函数需要传入父节点的值
- 实现
。确定递归函数的参数和返回值
- 参数：当前节点root，父节点的值
- 返回值：boolean，该子树的计算结果
。确定终止条件
- 当前节点是空时返回，当父节点为或操作时，返回false；当父节点为与操作时，返回true；
。确定单层递归的逻辑
- 当节点是叶子节点时，根据值返回true和false
- 当节点不是叶子节点使，继续dfs搜索
/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public boolean evaluateTree(TreeNode root) { return dfs(root, 2); } public boolean dfs (TreeNode root, int pre){ if (root == null){ if (pre == 2) return false;// or else return true;// and } if (root.val == 2) { return dfs(root.left, 2) || dfs(root.right, 2); } else if (root.val == 3){ return dfs(root.left, 3) && dfs(root.right, 3); } return root.val == 1; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
- 优化：不需要记录父节点的值，二叉树为完整二叉树
class Solution { public boolean evaluateTree(TreeNode root) { if (root.left == null) { return root.val == 1; } if (root.val == 2) { return evaluateTree(root.left) || evaluateTree(root.right); } else { return evaluateTree(root.left) && evaluateTree(root.right); } } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/evaluate-boolean-binary-tree/solutions/2091770/ji-suan-bu-er-er-cha-shu-de-zhi-by-leetc-4g8f/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
