深圳网站制作需要多少钱教育培训机构加盟
给你一棵 完整二叉树 的根节点，这棵树有以下特征：
- 叶子节点 要么值为 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）来计算当前节点的布尔值。 - 然后，这个值会被返回给当前节点的父节点的递归调用。
- 在回溯过程中，我们根据当前节点的运算符（2或3）和左右孩子的值（
- 终止：
- 递归会在所有叶子节点都被访问并处理完毕后终止。由于树是有限的，递归调用最终会耗尽所有的节点，并返回到最初的调用点（即根节点的递归调用）。
- 结果：
- 最终，根节点的递归调用会返回一个布尔值，这个值就是整个树的逻辑运算结果。
注意事项
- 递归函数必须有一个明确的终止条件（基本情况），否则会导致无限递归和栈溢出。
- 在递归调用中，我们实际上是在将问题分解成更小的子问题来解决。
- 递归的关键在于理解函数调用的栈行为，以及每个递归调用如何与它的子调用和父调用相关联。