外贸网站搭建推广,网站维护是什么,做模板网站的公司,网站建设 天佩营销目录
关于dfs
部分OJ题详解
2331. 计算布尔二叉树的值
129. 求根节点到叶节点数字之和
814. 二叉树剪枝
98. 验证二叉搜索树
230. 二叉搜索树中第K小的元素
257. 二叉树的所有路径 关于dfs
算法学习#xff08;十二#xff09;—— 递归#xff0c;搜索#xff0c…目录
关于dfs
部分OJ题详解
2331. 计算布尔二叉树的值
129. 求根节点到叶节点数字之和
814. 二叉树剪枝
98. 验证二叉搜索树
230. 二叉搜索树中第K小的元素
257. 二叉树的所有路径 关于dfs
算法学习十二—— 递归搜索回溯前置_数组递归查找-CSDN博客
部分OJ题详解
2331. 计算布尔二叉树的值
2331. 计算布尔二叉树的值 - 力扣LeetCode 题目有点长得结合示例来理解。下面来分析下这道题
看到二叉树遍历最先想到的就是递归这里我们用DFS来尝试解决在这道题的树中只要节点有孩子那必定有两个子节点没有只有一个子节点的情况非叶结点里面存的是“逻辑与”或“逻辑或”叶子节点存的就是1或0也就是“true”或“false”然后就是发现子问题的过程了以根节点为例假如我要知道根节点最后的值是什么那我就得直到左子树和右子树的值是多少然后以左子树或右子树的根节点为例再往下进行同样的分析就发现了我们的相同子问题所以我们的函数头就是bool dfs(root); 也就是你给我一个根节点我告诉你最后的结果是true还是false然后就是函数体的设计bool left dfs(root-left); bool right dfs(root-right); 也就是要告诉我们左右子树的值然后就是根据目前的根节点是“逻辑与”还是“逻辑或”算出结果最后就是递归出口就是当我遇到叶子节点的时候直接返回true或false即可
class Solution {
public:bool evaluateTree(TreeNode* root) {return dfs(root); }bool dfs(TreeNode* root){if(root-left nullptr) return root-val 0 ? false : true;bool left dfs(root-left);bool right dfs(root-right);if(root-val 2) return left | right;else return left right;}
};
129. 求根节点到叶节点数字之和 129. 求根节点到叶节点数字之和 - 力扣LeetCode 下面来分析下这道题
我们仍然还是尝试用递归的dfs来尝试解决下还是那三个步骤找相同子问题搞清楚每个子问题要做什么递归出口首先是相同子问题上面示例的树太小了我们换个大的树如下图所以函数头设计为int dfs(root, presum); 也就是传一个根节点以及这个根节点前面路径的值presum传给后面然后给我返回这个根节点最后计算的值函数体的步骤就是①先算出该根节点加上前面路径的计算结果值 ②把这个值传给左子树 ③把这个值传给右子树 ④左右子树返回计算结果 递归出口就是当遇到叶子节点时把上面的第一步计算完之后再正式返回不再将这个值传给左右子树
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root, 0);}int dfs(TreeNode* root, int prevsum){prevsum prevsum * 10 root-val; //①if(root-left nullptr root-right nullptr) return prevsum; //递归出口int ret 0;if(root-left ! nullptr) ret dfs(root-left, prevsum); //②if(root-right ! nullptr) ret dfs(root-right, prevsum); //③return ret; //④}
};
814. 二叉树剪枝
814. 二叉树剪枝 - 力扣LeetCode 题目的意思很明确就是如果一个节点的子树中没有值为1的节点的话就把这个子树干掉下面我们来分析下这道题
这个题目和我们之前的题目有点不一样前面的题目就是让我们根据信息求值没有改变二叉树而这个题目是要求我们实实在在的对二叉树做了修改了。还是用递归的dfs来尝试解决这道题还是三个问题先来看下如何找到相同的子问题当我遍历到一个节点时我们要做的就是“这个节点是否应该被剪掉”依据就是“这个节点的子树是否含有值为1的节点”所以这道题一定是后序遍历因为只有后序遍历才有机会回到根节点的时候带着左右子树的信息当遍历到叶节点时已经没有左右子树了并且如果我自己也是0就把我自己干掉回到父节点后还要修改下父节点的指针这一步可以通过返回值解决就是把父节点的指针修改成这个返回值即可所以函数头需要有一个返回值Node*如果已经是叶节点但我自己是1那么就不需要把我干掉就把我自己的指针向上返回就一直通过上面的步骤就可以干掉所有符合要求的子树所以函数头的设计就是Node* dfs(root);然后就是函数体的设置基本步骤和上面的一样①处理左子树 ②处理右子树 ③判断是否为叶结点并且判断是否为1进行剪枝操作并返回最后是递归出口就是当root null 的时候直接返回
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {return dfs(root);}TreeNode* dfs(TreeNode* root){if(root nullptr) return root;root-left dfs(root-left);root-right dfs(root-right);if(root-left nullptr root-right nullptr root-val 0)root nullptr;return root;}
};
98. 验证二叉搜索树
98. 验证二叉搜索树 - 力扣LeetCode 这道题我们主要是理解三个点①理解全局变量的优势 ②回溯 ③剪枝后面会给出两种思路和代码一个是有剪枝的一种没有剪枝下面来分析下这道题 二叉搜索树的中序遍历结果是一个有序的序列所以我们可以验证这棵树的中序遍历结果是否有序即可这个可以用一个全局变量来搞先搞一个全局变量 “prev 负无穷大”然后每次中序遍历时都更新一下 prev的值以上面的示例2为例根据中序遍历假设遍历到4的位置prev此时的值为3然后将此时节点的值和prev作比较验证有序即可最后就是遍历到5prev再次更新为4再次比较即可所以只要和prev作比较然后返回true或false即可 策略一也就是上面的方法 验证左子树是二叉搜索树当前遍历的节点符合二叉搜索树的定义验证右子树是二叉搜索树 策略二剪枝 还是以示例二为例假设递归已经完成了验证左子树是二叉搜索树此时prev是5当中序遍历到3时3小于5所以已经不符合二叉搜索树的定义了此时我们直接一路返回false到根节点不再去比较节点6了这就是剪枝意义就是加快搜索过程 无剪枝代码
class Solution
{
public:long prev LONG_MIN;bool isValidBST(TreeNode* root) {return dfs(root); }bool dfs(TreeNode* root){if(root nullptr) return true;bool left dfs(root-left);bool cur false; //cur表示当前节点是否满足二叉搜索树条件if(root-val prev) cur true;prev root-val;bool right dfs(root-right);return left right cur;}
}; 剪枝
class Solution
{
public:long prev LONG_MIN;bool isValidBST(TreeNode* root) {return dfs(root); }bool dfs(TreeNode* root){if(root nullptr) return true;bool left dfs(root-left);if(left false) return false; //剪枝就是当左子树已经不符合搜索二叉树了直接返回bool cur false; //cur代表当前节点是否满足二叉搜索树条件if(root-val prev) cur true;if(cur false) return false; //如果我当前位置节点已经不符合二叉搜索树要求了直接返回不再去遍历右子树了这就是剪枝prev root-val;bool right dfs(root-right);return left right cur;}
};
230. 二叉搜索树中第K小的元素
230. 二叉搜索树中第 K 小的元素 - 力扣LeetCode 这道题题意还是很简单的也是给我们一个二叉搜索树然后让我们返回这个树的节点中值第K小的值下面来分析下这道题
有了上一道题的经验之后这道题其实超级简单因为我们已经知道了“二叉搜索树的中序遍历结果是有序的”所以我们就可以用“ 两个全局遍历 中序遍历 ”就可以解决这道题以上面的示例二为例搞两个全局遍历count k 3ret 0ret的作用就是当count一直减减到0时用ret标记一下当前节点的值然后返回这里可以用剪枝就是当count为0时直接返回后面的步骤都不再执行这就是剪枝这一步加个判断即可 class Solution {
public:int count;int ret;int kthSmallest(TreeNode* root, int k) {count k;dfs(root);return ret;}void dfs(TreeNode* root){if(root nullptr || count 0) return;dfs(root-left);count--;if(count 0) ret root-val;dfs(root-right);}
};
257. 二叉树的所有路径
257. 二叉树的所有路径 - 力扣LeetCode 前面两道题我们提到了三个词①全局变量 ②回溯 ③剪枝其中回溯有个性质叫做“恢复现场” 关于恢复现场 网上很多人在自学算法的时候都是看到了代码中有“恢复现场”的操作才知道这道题用了“回溯”所以很多人以为的就是“恢复现场 -- 回溯” 而今天我们就要把这个因果关系给反过来 如果有递归那么肯定有回溯递归 -- 回溯如果有回溯那么肯定有“恢复现场”回溯 -- 恢复现场所以如果有递归那么就有恢复现场递归 -- 恢复现场 在后面的难度较高的递归回溯题目的时候有了“回溯 -- 恢复现场”的思路之后写代码的过程才会有思路并且一旦我们在题目中用到了全局变量那么恢复现场的操作就会显得很重要 这个题目很简单就是让我们把每一个路径保存在一个字符串数组里面具体步骤通过示例一和示例二很好理解下面来分析下这道题
思路很简单就是在搜索的过程中记录每一个节点即可当遇到叶子节点的时候停止搜索我们可以搞两个全局变量①一个字符串数组 string[] ret就是在我遍历时发现叶子节点时就把结果扔 ret 里去 ②一个字符串变量 string path作用就是在深度遍历的时候记录一下路径以示例一为例遍历到1时path的值为“1-”当遍历到2时path的值为“1-2”当遍历到5时由于5是叶节点所以只添加数字所以最后path的值为“1-2-5”但是前面说过有递归就有回溯当遍历完5回溯到1时接下来就是要往右边回溯但是此时path的值不是从1开始的“1-”而是还是之前的“1-2-5”所以我们需要“恢复现场”就是我们在向上返回的时候需要不断pop掉path的结尾但是又因为是全局path需要很多很多次的添加和删除不太好控制所以这道题我们不用全局的path后面再用那么用什么代替全局path呢我们可以在函数头设置一下void dfs(root, path); 如果我们把path当作参数传递那么就是每次调用path的时候相当于重新创建了一个path变量也就是每次深度搜索时都用的是自己单独地path变量代替了“恢复现场”的操作和功能然后激素关心一下每一个子问题在干什么也激素函数体的设置如果root是叶子节点只在path后面添加上数字即可如果root不是叶子节点dfs(root-left, path); dfs(root-right, path)最后就是递归出口就是注意一下剪枝当左子树为空时就不需要再 dfs(root-left)了直接去搞右子树即可if(root nullptr) return;
class Solution {
public:vectorstring ret;vectorstring binaryTreePaths(TreeNode* root) {string path;if(root nullptr) return ret;dfs(root, path);return ret;}void dfs(TreeNode* root, string path){path to_string(root-val);if(root-left nullptr root-right nullptr) //如果是叶子节点直接返回不再搜索{ret.push_back(path);return;}path -;if(root-left) dfs(root-left, path);if(root-right) dfs(root-right, path);}
};
