网站建设大宇,wordpress怎么设置静态主页,网站描述修改,手机百度账号登录个人中心给你一棵 完整二叉树 的根节点#xff0c;这棵树有以下特征#xff1a;
叶子节点 要么值为 0 要么值为 1 #xff0c;其中 0 表示 False #xff0c;1 表示 True 。非叶子节点 要么值为 2 要么值为 3 #xff0c;其中 2 表示逻辑或 OR #xff0c;3 表示逻辑与 AND 。
…给你一棵 完整二叉树 的根节点这棵树有以下特征
叶子节点 要么值为 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对应false1对应true。递归情况 当我们遇到一个非叶子节点时即节点的值为2或3我们需要计算其左右孩子的值。我们通过递归调用evaluateTree函数来计算左孩子的值leftValue和右孩子的值rightValue。在递归调用中我们实际上是在处理一个更小的子问题计算一个子树的根节点的布尔值。递归调用会继续进行直到我们遇到叶子节点为止。一旦我们到达叶子节点递归就会开始回溯每个递归调用都会返回一个布尔值给它的调用者。回溯 在回溯过程中我们根据当前节点的运算符2或3和左右孩子的值leftValue和rightValue来计算当前节点的布尔值。然后这个值会被返回给当前节点的父节点的递归调用。终止 递归会在所有叶子节点都被访问并处理完毕后终止。由于树是有限的递归调用最终会耗尽所有的节点并返回到最初的调用点即根节点的递归调用。结果 最终根节点的递归调用会返回一个布尔值这个值就是整个树的逻辑运算结果。
注意事项
递归函数必须有一个明确的终止条件基本情况否则会导致无限递归和栈溢出。在递归调用中我们实际上是在将问题分解成更小的子问题来解决。递归的关键在于理解函数调用的栈行为以及每个递归调用如何与它的子调用和父调用相关联。
