当前位置：首页 > news >正文

计算布尔二叉树的值

news 2024/11/5 11:44:14

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

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

计算一个节点的值方式如下：如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False 。否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。返回根节点 root 的布尔运算值。

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

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

解题思路

递归是解决这个问题的一个关键部分。在二叉树的相关问题中，递归经常被用来遍历树结构，因为它允许我们在不显式使用栈或队列的情况下，通过函数调用栈隐式地维护一个访问节点的顺序。

定义节点结构：
使用TreeNode结构来表示树的节点，包含节点的值和左右孩子指针。
递归遍历：
使用递归函数遍历树的节点。对于每个节点，根据其值判断是叶子节点还是非叶子节点，并分别处理。
逻辑运算：
- 如果节点是叶子节点（值为0或1），直接返回对应的布尔值。
- 如果节点是非叶子节点，根据其值（2或3）分别进行逻辑或和逻辑与运算，并返回结果。

bool evaluateTree(TreeNode* root) {  // 基本情况（叶子节点）  if (root->val == 0) {  return false;  } else if (root->val == 1) {  return true;  }  // 递归情况（非叶子节点）  // 对于非叶子节点，我们需要计算其左右孩子的值  bool leftValue = evaluateTree(root->left);  // 递归调用，计算左孩子的值  bool rightValue = evaluateTree(root->right); // 递归调用，计算右孩子的值  // 根据当前节点的运算符（由 val 决定），返回相应的逻辑运算结果  if (root->val == 2) {  // 当前节点是逻辑或 OR 运算符  return leftValue || rightValue;  } else if (root->val == 3) {  // 当前节点是逻辑与 AND 运算符  return leftValue && rightValue;  }  // 理论上不会执行到这里，因为题目已经限定节点值只能是0, 1, 2, 3  // 但为了代码的健壮性，最好还是加上这个返回语句  return false; // 这是一个默认返回，实际上不会被执行  
}

递归的拆解

基本情况：
- 当我们遇到一个叶子节点时（即节点的值为0或1），我们不需要再递归调用，因为叶子节点没有孩子。我们直接返回该节点的布尔值（0对应false，1对应true）。
递归情况：
- 当我们遇到一个非叶子节点时（即节点的值为2或3），我们需要计算其左右孩子的值。
- 我们通过递归调用evaluateTree函数来计算左孩子的值（leftValue）和右孩子的值（rightValue）。
- 在递归调用中，我们实际上是在处理一个更小的子问题：计算一个子树的根节点的布尔值。
- 递归调用会继续进行，直到我们遇到叶子节点为止。一旦我们到达叶子节点，递归就会开始回溯，每个递归调用都会返回一个布尔值给它的调用者。
回溯：
- 在回溯过程中，我们根据当前节点的运算符（2或3）和左右孩子的值（leftValue和rightValue）来计算当前节点的布尔值。
- 然后，这个值会被返回给当前节点的父节点的递归调用。
终止：
- 递归会在所有叶子节点都被访问并处理完毕后终止。由于树是有限的，递归调用最终会耗尽所有的节点，并返回到最初的调用点（即根节点的递归调用）。
结果：
- 最终，根节点的递归调用会返回一个布尔值，这个值就是整个树的逻辑运算结果。