1. 计算二叉树中的布尔值
题目链接：2331. 计算布尔二叉树的值
题目内容
给你一棵完整二叉树的根，这棵树有以下特征：
- 叶子节点要么值为 0 要么值为 1，其中 0 表示 False，1 表示 True。
- 非叶子节点要么值为 2 要么值为 3，其中 2 表示逻辑或 OR，3 表示逻辑与 AND。
计算一个节点的值方式如下：
- 如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False。
- 否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。
返回根节点 root 的布尔运算值。
完整二叉树是每个节点有 0 个或者 2 个孩子的二叉树。叶子节点是没有孩子的节点。
输入：root = [2,1,3,null,null,0,1] 输出：true 解释：上图展示了计算过程。AND 与运算节点的值为 False AND True = False。OR 运算节点的值为 True OR False = True。根节点的值为 True，所以我们返回 true。
示例 2： 输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false。
提示：
- 树中节点数目在 [1, 1000] 之间。
- 0 <= Node.val <= 3
- 每个节点的孩子数为 0 或 2。
- 叶子节点的值为 0 或 1。
- 非叶子节点的值为 2 或 3。
分析
要想知道根节点的布尔值，就得先求左子树和右子树的布尔值。
递归代码步骤
- 大量重复子问题 (函数头):
boolean dfs(TreeNode root) - 只关注某一个子问题: 想知道根节点的布尔值，就得先求左子树和右子树的布尔值。
- 递归出口:
- 节点值为 0，返回 false
- 节点值为 1，返回 true
代码实现
class Solution {
public boolean evaluateTree(TreeNode root) {
return dfs(root);
}
public boolean dfs(TreeNode root) {
if (root.val == 0) {
return false;
}
if (root.val == 1) {
return true;
}
boolean left = dfs(root.left);
boolean right = dfs(root.right);
return root.val == 2 ? left | right : left & right;
}
}
2. 求根节点到叶节点数字之和
题目链接：129. 求根节点到叶节点数字之和
题目内容
给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。 计算从根节点到叶节点生成的所有数字之和。
叶节点是指没有子节点的节点。
示例 1：
输入：root = [1,2,3]
输出：25
解释：从根到叶子节点路径 1->2 代表数字 12，从根到叶子节点路径 1->3 代表数字 13。因此，数字总和 = 12 + 13 = 25
示例 2：
输入：root = [4,9,0,5,1]
输出：1026
解释：从根到叶子节点路径 4->9->5 代表数字 495，从根到叶子节点路径 4->9->1 代表数字 491，从根到叶子节点路径 4->0 代表数字 40。因此，数字总和 = 495 + 491 + 40 = 1026
提示：
- 树中节点的数目在范围 [1, 1000] 内
- 0 <= Node.val <= 9
- 树的深度不超过 10
分析题意
以上图得 1 节点为例：
- 需要接收来自上一层的 49。
- 需要往下传递 49*10+1=491。
- 到达叶子节点，需要将结果返回。 分析出这三点，就不难写出递归代码了。
具体步骤
- 大量重复子问题 (函数头): 上一层节点×10+根节点传给子节点。直到叶子节点才返回最终结果。
int dfs(root, presum)。presum 记录上一层的值。 - 某一子问题的工作流程:
- 计算当前的值，presum*10+root.val;
- 前序遍历递归左子树
- 前序遍历递归右子树
- 递归出口: 当前节点为叶子节点时，返回结果。
代码实现
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int presum) {
presum = presum * 10 + root.val;
if (root.left == null && root.right == null) {
return presum;
}
int ret = 0;
if (root.left != null) {
ret += dfs(root.left, presum);
}
if (root.right != null) {
ret += dfs(root.right, presum);
}
return ret;
}
}
总结
凡是能用递归来解决的二叉树题目，要么是前序遍历，要么是后序遍历，还有一部分是中序遍历。大部分题都是这样的，一般可以先尝试前序，再后序，最后中序。
