【二叉树的深搜】计算布尔二叉树的值求根节点到叶节点数字之和

文章目录

2331. 计算布尔二叉树的值
解题思路：后序遍历
129. 求根节点到叶节点数字之和
解题思路：深度优先搜索 + 前序遍历

2331. 计算布尔二叉树的值

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

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

计算一个节点的值方式如下：

如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False 。
否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。

返回根节点 root 的布尔运算值。

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

叶子节点 是没有孩子的节点。

示例 1：

输入：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 。

解题思路：后序遍历

根据题目的分析，我们对于叶子节点和非叶子节点需要有不同的处理，当我们遍历到叶子节点的时候，其实就可以直接返回 node->val 了，因为此时 0 代表 false，1 代表 true，刚刚好和布尔值是一样的，所以我们可以直接返回 node->val 即可！并且因为这道题的二叉树是完整二叉树，也就是一个节点要么左右孩子都存在，要么就是叶子节点，所以我们只需要判断一下 node->left 或者 node->right 存不存在即可判断是否为叶子节点！

而对于非叶子节点，它是逻辑操作，需要有左右子树的计算结果才能执行，所以就得使用后序遍历，先拿到左右子树的计算结果，然后判断一下当前非叶子节点是按位或还是按位与操作，进行不同的返回结果即可！

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool evaluateTree(TreeNode* root) {// 递归函数出口if(root->left == nullptr || root->right == nullptr)return root->val;// 先进行后序遍历bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);// 再处理当前节点if(root->val == 2)return left | right;elsereturn left & right;}
};

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

解题思路：深度优先搜索 + 前序遍历

因为我们得知道从根节点到每个叶子节点的路径代表的数字和，所以我们就得使用前序遍历来遍历整棵二叉树，在遍历过程中需要有一个变量 tmp 来记录当前走过的路径代表的数。

然后我们只需要判断当前节点是否为叶子节点，是的话直接将最后该叶子节点和 tmp 进行运算后返回给上一层即可；如果不是的话，说明此时还没到可以返回的时机，则递归到左右子树去处理，直到走到叶子节点然后遍历完整棵二叉树为止！

在遍历期间要注意的是我们可以不需要在递归函数开头给出递归函数的出口，因为题目节点个数是大于零的，所以保证一开始是不会访问空指针的，我们只需要在递归左右子树之前判断左右孩子节点是否存在即可，其它的没啥大问题！

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root, 0);}int dfs(TreeNode* root, int tmp){// 进行先序遍历处理，只不过是专门对叶子节点处理// 因为题目节点个数是大于零的，所以保证不会访问空指针tmp = tmp*10 + root->val; if(root->left == nullptr && root->right == nullptr)return tmp;// 如果不是叶子节点的话，则继续递归左右子树，并且将左右子树的结果累加到ret上进行返回int ret = 0;if(root->left)  ret += dfs(root->left, tmp);if(root->right) ret += dfs(root->right, tmp);return ret;}
};

这里还有另一种写法，就是我们的递归函数可以不搞返回值，而是用一个变量 sum 来记录路径代表数的总和，要注意的是形参是一个地址或者引用，这样子才能保证全局累加的时候是对同一个 sum 进行累加！

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumNumbers(TreeNode* root) {int sum = 0;dfs(root, 0, sum);return sum;}void dfs(TreeNode* root, int tmp, int& sum){// 进行先序遍历处理，只不过是专门对叶子节点处理sum += tmp*10 + root->val;if(root->left == nullptr && root->right == nullptr)return;if(root->left)  dfs(root->left, tmp*10 + root->val, sum);if(root->right) dfs(root->right, tmp*10 + root->val, sum);}
};