【刷题】初步认识深搜（DFS）

---

dfs算法

深度优先搜索（DFS）是一种常用的搜索算法，它通过尽可能深地搜索树的分支，来寻找解决方案。由于其简单和易于实现的特性，DFS成为解决问题的强大工具，尤其是在数据规模较小的情况下。数据在100以内一般使用DFS

运行原理： DFS算法的核心思想是从一个起点开始，沿着树的边走到尽可能深的分支上，然后回溯到之前的分叉点，寻找未探索的分支，对不满足条件的分支进行剪枝。这个过程重复进行，直到找到解决方案或探索完所有可能的路径。DFS通常使用递归实现，这使得代码简洁易读。

dfs算法其实我们一点也不陌生，早在二叉树的学习中，用于遍历二叉树的前序遍历，中序遍历，后序遍历都是使用的dfs算法，所以dfs并不神秘！！！我们接下来在实际应用中来加强对dfs算法的认识。

二叉树中的深搜

我准备了以下题目，我们一起来看看吧：

Leetcode 129. 求根节点到叶节点数字之和

家人们！上链接：129. 求根节点到叶节点数字之和

题目描述

根据题目，每条路径都是一个数字，我们要做的是将每条路径的数字加起来得到一个和。

算法思路

我们的工作就是得到每条路径的数字，而得到这些数字的最简单的办法就是使用dfs算法，一条一条的搜索下去。

使用dfs算法我们需要明白dfs函数体是对一个节点的处理，我们要顾全好大局，避免出现不必要的错误。
通常我们使用全局变量来优化我们的dfs函数体，通过全局变量，就不需要传递过多的参数了。

class Solution {
public://int sumNumbers(TreeNode* root) {vector<long long > nums;dfs(nums ,0 , root);long long  ans = 0 ;for(auto s : nums)ans += s;return ans;}void dfs(vector<long long >& nums , long long bef , TreeNode* root){if(root == nullptr) return ;if(root->left == nullptr && root->right == nullptr){bef *= 10;nums.push_back(bef + root->val);}dfs(nums , bef * 10 + root->val , root->left);dfs(nums , bef * 10 + root->val , root->right);}
};

提交：过啦！！！

Leetcode 814. 二叉树剪枝

上链接：814. 二叉树剪枝

题目描述

本题需要我们对二叉树进行判断，将不满足条件的进行剪枝操作。

算法思路

我们主要需要进行两步：判断与剪枝

1. 判断需要对子树进行判断是否有1；
2. 剪枝就直接将指向设置为nullptr即可；

dfs的函数体只针对当前节点进行判断，我们要相信其中的dfs可以解决后续问题。

1. 首先需要对当前节点进行判断，如果为空直接返回空指针！
2. 然后我们需要对左右子树进行判断，判断的结果时（子树满足条件就是原本的子树，反之是nullptr）
3. 对左右子树检查好了，就要检查当前节点，如果左右子树都为空了，并且当前节点的数字还是 0 ，直接进行删除！

其实这套算法的本质是后序遍历，从叶子节点开始向上删除。

class Solution {
public:TreeNode* pruneTree(TreeNode* root) {return dfs(root);}TreeNode* dfs(TreeNode* root){//后序遍历//返回值决定上层是否删除if(root == nullptr) return nullptr;//是叶子节点才返回else {//该层处理root->left = dfs(root->left);root->right = dfs(root->right);if(!root->right && !root->left && root->val == 0 ) return nullptr;else return root;}}
};

提交：过啦！！！

Leetcode 98. 验证二叉搜索树

上连接：98. 验证二叉搜索树

题目描述

这题对于我们学过二叉搜索树，AVL树，红黑树的简直是小菜一碟！

算法思路

二叉搜索树有一个重要的性质：中序遍历会得到有序数据。
所以判断是否为二叉搜索树就可以通过这个性质来判断，我们模拟进行中序遍历：

1. 中序遍历的核心是先左子树 ，再当前节点 ，最后是右子树
2. 那么为了快速进行判断是否有序，我们肯定不能把所有的数据都遍历一遍再判断是否有序！而是在遍历的过程中就完成判断的过程！
3. 判断是否有序就是比较当前数是否比它之前那个数大！那么如何获取之前的数呢？很简单，因为我们是以模拟中序遍历，很自然的就可以获取到当前节点之前的那个数！
4. 记住 ： dfs函数体只需要考虑如何解决当前节点！！！不要多考虑！

class Solution {
public://使用全局变量来记录 上一个节点的值long long prev = LONG_MIN ; bool isValidBST(TreeNode* root) {return dfs(root);}//dfs函数bool dfs(TreeNode* root){//如果为空就直接返回if(root == nullptr) return true;//通过中序遍历解决问题//对左进行判断bool l = dfs(root->left);if(!l) return false;//对当前节点进行判断if(root->val <= prev) return false;//再当前节点更新 prevprev = root->val;//对右边进行判断bool r = dfs(root->right);if(!r) return false;return l && r;}
};

提交：过啦！！！
再分析一个中序遍历的题目，框架是一致的：230. 二叉搜索树中第K小的元素

Leetcode 257. 二叉树的所有路径

上链接：257. 二叉树的所有路径

题目描述

非常好理解的题目奥

算法思路

这道题的思路很简单，把所有的路径都遍历一遍就可以了！
注意细节的处理：

1. 路径何时加上->才能保证不会多加？ 再当前节点不为空，将val一起插入，还有左右子树再插入->即可
2. 何时路径结束？ 到叶子节点就结束！
3. 注意回溯的问题！！！

class Solution {
public:vector<string> ans;vector<string> binaryTreePaths(TreeNode* root) {string path = "";dfs(path , root);return ans;}void dfs(string path , TreeNode* root){if(root == nullptr) return ;path += to_string(root->val);if(!root->left && !root->right) {ans.push_back(path);return ;}path += "->";//对左边进行处理 if(root->left) dfs(path , root->left);//对右边进行处理if(root->right) dfs(path , root->right);}
};

提交过啦！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！