计算布尔二叉树的值

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

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

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

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

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

解题思路

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

1. 定义节点结构：
   使用TreeNode结构来表示树的节点，包含节点的值和左右孩子指针。

2. 递归遍历：
   使用递归函数遍历树的节点。对于每个节点，根据其值判断是叶子节点还是非叶子节点，并分别处理。

3. 逻辑运算：

   • 如果节点是叶子节点（值为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; // 这是一个默认返回，实际上不会被执行  
}

 递归的拆解

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

注意事项

• 递归函数必须有一个明确的终止条件（基本情况），否则会导致无限递归和栈溢出。
• 在递归调用中，我们实际上是在将问题分解成更小的子问题来解决。
• 递归的关键在于理解函数调用的栈行为，以及每个递归调用如何与它的子调用和父调用相关联。