【刷题】初步认识深搜（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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

提交：过啦！！！

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;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

提交：过啦！！！

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;
        //再当前节点更新 prev
        prev = root->val;
        
        //对右边进行判断
        bool r = dfs(root->right);
        if(!r) return false;
        return l && r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

提交：过啦！！！
再分析一个中序遍历的题目，框架是一致的：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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

提交过啦！！！

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

下一篇文章见！！！