[Lc_2 二叉树dfs] 布尔二叉树的值 | 根节点到叶节点数字之和 | 二叉树剪枝

目录

1.计算布尔二叉树的值

题解

2.求根节点到叶节点数字之和

3. 二叉树剪枝

题解

---

1.计算布尔二叉树的值

链接：2331. 计算布尔二叉树的值

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

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

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

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

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

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

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

---

题解

给一颗完整二叉树，孩子节点要么是0要么是2，不存在1个孩子节点。

叶子节点和非叶子节点数字分别代表不同的意思，最后将root根结果bool值返回去。

解法：递归

宏观角度看待递归

当想知道root根节点bool值时

• 我要先知道左子树bool值，在知道右子树bool值，然后将左右子数的bool值和root本身信息做整合。
• 当我们要知道左子树和右子树的bool值，你会发现它和大问题是一样的。
• 大问题是解决整棵树的bool值，小问题是解决左子树bool值，右子树bool值。
• 此时把左指针传给dfs，dfs把左子树bool值给你，把右指针传给dfs，dfs把右子树bool值给你。

所以dfs非常好设计。

1. 函数头

bool dfs(TreeNode* root)

2. 函数体

先求左子树bool值，在求右子树bool，不要管递归如何执行，只需要知道你给它数据它一定能完成任务。

• bool left=dfs(root->left)
• bool right=dfs(root->right)

最后在将左子树和右子树bool值和root做整合。

3. 递归出口

到叶子节点就不需要往后递归了，此时返回结果就行了

/*** 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) {return dfs(root);}bool dfs(TreeNode* root){if(root->left == nullptr){return root->val;}bool left=dfs(root->left);bool right=dfs(root->right);return root->val == 2 ? left | right : left & right;
//叶子节点 才有值  其他都是操作符}
};

---

2.求根节点到叶节点数字之和

链接：129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

---

将根到叶子节点组合的数加起来

解法：递归

首先我们要找到 相同子问题，在树中相同子问题很好找，只需要关注递归到每一层需要干什么事情即可。

当它们干的都是一样的事情，这就是相同的子问题。

当递归到5这一层，我发现要拿到和5相连下面的叶子节点的数把它们加起来，然后返回给根节点。当到5这一层

• 首先要把12先给我传过来，不然我怎么算出1258，也就是到某一层要把它之前路径上之后给我传过来 tmp。然后拿到这个12，先算出125。
• 然后把125传给左边
• 把125传给右边
• 然后把左边值的和与右边值的和相加，return 上一层节点 ret

在这5这一层要完成4个任务，同理其他层也是要完成相同的任务。

1.函数头

首先要有一个返回值，就是传给dfs一个根节点把和它相连的叶子节点的和返回。

• 但是要注意的是，我们除了要传一个根节点，还需要再把递归到该层的上面路径和拿到！
• 因此函数头是int dfs(root，num)

2.函数体

1、2、3、4个步骤

3.递归出口

• 当到叶子节点就可以返回了，但是要注意的是，这个递归出应该在步骤1之后的
• 因为到叶子节点, 也要把叶子节点的数加上才向上返回的。

/*** 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);}//存上一层的numint dfs(TreeNode* root,int num){//更新  当前层数值num=num*10+root->val;//左右为空 就返回这个值if(!root->left && !root->right) return num;int ret=0;if(root->left) ret+=dfs(root->left,num);if(root->right) ret+=dfs(root->right,num);return ret;}
};

---

3. 二叉树剪枝

链接：814. 二叉树剪枝

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

---

题解

注意这里的剪枝和前面说的剪枝是不一样的，前面的是那条路不是通往终点的路不能在走了，这里的剪枝真的就是把分枝剪掉！

• 返回移除了所有 不包含 1 的子树 的原二叉树 的意思是，就是如果子树全是0就把它剪掉。
• 如果子数有1就不能剪掉。

通过决策树，抽象出递归的三个核心问题

也就是说通过，完成二叉树剪枝这个任务，完成递归三个核心问题。

• 像之前先把每个子问题要完成任务先找到，但是有时候某些道题非常麻烦，无法总结出子问题到底干了什么问题，这道题是给一个根节点然后把子树全为0剪掉然后把新根节点返回来。
• 但是有些题特别抽象你根本无法总结出来你让这个递归去完成什么任务，任务太多了。此时我们要有一个能力，通过研究递归的过程来总结出函数头、函数体、递归出口！

首先这肯定是一个后序遍历，先要确定左右子树是什么情况才能决定是否把这个子树干掉。

• 当作后序遍历到底最左节点，然后再后序发现它左为空右为空，然后自己本身也是0，说明可以给它剪枝。
• 然后回到上一层但是有一个问题，是不是要修改上一层左子树的指针啊，因此这个递归函数要有一个返回值 TreeeNode*。

然后如果左右子树都为空，但自己是1，说明不能剪枝

当我们把根左子树都弄好了，其实整个递归过程就出来。

函数头

• TreeNode* dfs(root) 给一个根节点，然后把结果给我

函数体

• 左子树右子树都搞完返回给我一个东西，然后通过返回值 再结合我自己看是否需要把自己删除。
• 1.左子树、2.右子树、 3.判断

递归出口

• 遇到null结束，就返回null

递归处理 树

• 你只需要管它是做什么的，拿去用，而不需要在意它是怎么实现的。
• 我们的pruneTree是用来将树去除不包含1的子树。
• 那么我们可以用它来干嘛？我们可以对root的左右子树都进行一次pruneTree，现在root的左右子树都是去除了不包含1的子树的子树或者null。
• 那么我们只需要判断什么？只需要在root不存在左右子树且自身为0时，返回null即可，如果root.val为1或者左右子树存在任一，都需要返回自身。

/*** 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:TreeNode* pruneTree(TreeNode* root) {//出口if(!root) return nullptr;root->left=pruneTree(root->left);//递归 左子树root->right=pruneTree(root->right);//递归 右子树//如果 当前是 叶子节点，且值为0，剪枝if(!root->left && !root->right && root->val==0)return nullptr;return root;}
};