---

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?(･ω･)ﾉ謝謝閱讀！！！

下一篇文章見！！！