深度优先搜索(DFS)是一种常用的搜索算法,它通过尽可能深地搜索树的分支,来寻找解决方案。由于其简单和易于实现的特性,DFS成为解决问题的强大工具,尤其是在数据规模较小的情况下。数据在100以内一般使用DFS
运行原理: DFS算法的核心思想是从一个起点开始,沿着树的边走到尽可能深的分支上,然后回溯到之前的分叉点,寻找未探索的分支,对不满足条件的分支进行剪枝。这个过程重复进行,直到找到解决方案或探索完所有可能的路径。DFS通常使用递归实现,这使得代码简洁易读。
dfs算法其实我们一点也不陌生,早在二叉树的学习中,用于遍历二叉树的前序遍历,中序遍历,后序遍历都是使用的dfs算法,所以dfs并不神秘!!!我们接下来在实际应用中来加强对dfs算法的认识。
我准备了以下题目,我们一起来看看吧:
家人们!上链接: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);
}
};
提交:过啦!!!
上链接:814. 二叉树剪枝
本题需要我们对二叉树进行判断,将不满足条件的进行剪枝操作。
我们主要需要进行两步:判断与剪枝
dfs的函数体只针对当前节点进行判断,我们要相信其中的dfs可以解决后续问题。
其实这套算法的本质是后序遍历,从叶子节点开始向上删除。
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;
}
}
};
提交:过啦!!!
上连接:98. 验证二叉搜索树
这题对于我们学过二叉搜索树,AVL树,红黑树的简直是小菜一碟!
二叉搜索树有一个重要的性质:中序遍历会得到有序数据。 所以判断是否为二叉搜索树就可以通过这个性质来判断,我们模拟进行中序遍历:
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小的元素
上链接: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);
}
};
提交过啦!!!