【刷题】初步认识深搜（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；
- 剪枝就直接将指向设置为nullptr即可；
dfs的函数体只针对当前节点进行判断，我们要相信其中的dfs可以解决后续问题。
- 首先需要对当前节点进行判断，如果为空直接返回空指针！
- 然后我们需要对左右子树进行判断，判断的结果时（子树满足条件就是原本的子树，反之是nullptr）
- 对左右子树检查好了，就要检查当前节点，如果左右子树都为空了，并且当前节点的数字还是 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树，红黑树的简直是小菜一碟！
算法思路
二叉搜索树有一个重要的性质：中序遍历会得到有序数据。 所以判断是否为二叉搜索树就可以通过这个性质来判断，我们模拟进行中序遍历：
- 中序遍历的核心是先左子树 ，再当前节点 ，最后是右子树
- 那么为了快速进行判断是否有序，我们肯定不能把所有的数据都遍历一遍再判断是否有序！而是在遍历的过程中就完成判断的过程！
- 判断是否有序就是比较当前数是否比它之前那个数大！那么如何获取之前的数呢？很简单，因为我们是以模拟中序遍历，很自然的就可以获取到当前节点之前的那个数！
- 记住 ： 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;
//再当前节点更新 prev
prev = root->val;
//对右边进行判断
bool r = dfs(root->right);
if(!r) return false;
return l && r;
}
};提交：过啦！！！ 再分析一个中序遍历的题目，框架是一致的：230. 二叉搜索树中第K小的元素
Leetcode 257. 二叉树的所有路径
上链接：257. 二叉树的所有路径
题目描述
非常好理解的题目奥
算法思路
这道题的思路很简单，把所有的路径都遍历一遍就可以了！ 注意细节的处理：
- 路径何时加上
->才能保证不会多加？ 再当前节点不为空，将val一起插入，还有左右子树再插入->即可 - 何时路径结束？ 到叶子节点就结束！
- 注意回溯的问题！！！
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);
}
};提交过啦！！！
腾讯云开发者
