“

????這是本人第45篇原創博文，每周至少兩篇更新，謝謝賞臉閱讀文章

今天來聊聊 dfs 的解題方法，這些方法都是總結之后的出來的經驗，有值得借鑒的地方。

1 從二叉樹看 dfs

二叉樹的思想其實很簡單，我們剛剛開始學習二叉樹的時候，在做二叉樹遍歷的時候是不是最常見的方法就是遞歸遍歷，其實，你會發現，二叉樹的題目的解題方法基本上都是遞歸來解題，我們只需要走一步，其他的由遞歸來做。

我們先來看一下二叉樹的前序遍歷、中序遍歷、后序遍歷的遞歸版本。

//前序遍歷 void?traverse(TreeNode?root)?{System.out.println(root.val);traverse(root.left);traverse(root.right); }//中序遍歷 void?traverse(TreeNode?root)?{traverse(root.left);System.out.println(root.val);traverse(root.right); }//后續遍歷 void?traverse(TreeNode?root)?{traverse(root.left);traverse(root.right);System.out.println(root.val); }

其實你會發現，二叉樹的遍歷的過程就能夠看出二叉樹遍歷的一個整體的框架，其實這個也是二叉樹的解題的整體的框架就是下面這樣的。

void?traverse(TreeNode?root)?{//這里將輸出變成其他操作，我們只完成第一步，后面的由遞歸來完成。traverse(root.left);traverse(root.right); }

我們在解題的時候，我們只需要去想當前的操作應該怎么實現，后面的由遞歸去實現，至于用前序中序還是后序遍歷，由具體的情況來實現。

下面來幾個二叉樹的熱身題，來體會一下這種解題方法。

1. 如何把?叉樹所有的節點中的值加?

首先還是一樣，我們先寫出框架。

void?traverse(TreeNode?root)?{//這里將輸出變成其他操作，我們只完成第一步，后面的由遞歸來完成。traverse(root.left);traverse(root.right); }

接下來，考慮當前的一步需要做什么事情，在這里，當然是給當前的節點加一。

void?traverse(TreeNode?root)?{if(root?==?null)?{return;}//這里改為給當前的節點加一。root.val?+=?1;traverse(root.left);traverse(root.right); }

發現是不是水到渠成？

不爽？再來一個簡單的。

2. 如何判斷兩棵?叉樹是不是同一棵二叉樹

這個問題我們直接考慮當前一步需要做什么，也就是什么情況，這是同一顆二叉樹？

1）兩棵樹的當前節點等于空：root1 == null && root2 == null，這個時候返回 true。2）兩棵樹的當前節點任意一個節點為空：root1 == null || root2 == null，這個時候當然是 false。3）兩棵樹的當前節點都不為空，但是 val 不一樣：root1.val != root2.val，返回 false。

所以，答案就顯而易見了。

boolean?isSameTree(TreeNode?root1,?TreeNode?root2)?{//?都為空的話if?(root1?==?null?&&?root2?==?null)?return?true;//??個為空，?個?空if?(root1?==?null?||?root2?==?null)?return?false;//?兩個都?空，但?val?不?樣if?(root1.val?!=?root2.val)?return?false;//?遞歸去做return?isSameTree(root1.left,?root2.left)?&&?isSameTree(root1.right,?root2.right); }

有了上面的講解，我相信你已經有了基本的思路了，下面我們來點有難度的題目，小試牛刀。

3. leetcode中等難度解析

114. 二叉樹展開為鏈表

這個題目是二叉樹中的中等難度題目，但是通過率很低，那么我們用上面的思路來看看是否可以輕松解決這個題目。

這個題目乍一看，根據前面的思路，你可以能首先會選擇前序遍歷的方式來解決，是可以的，但是，比較麻煩，因為前序遍歷的方式會改變右節點的指向，導致比較麻煩，那么，如果前序遍歷不行，就考慮中序和后序遍歷了，由于，在展開的時候，只需要去改變左右節點的指向，所以，這里其實最好的方式還是用后續遍歷，既然是后續遍歷，那么我們就可以快速的把后續遍歷的框架寫出來了。

public?void?flatten(TreeNode?root)?{if(root?==?null){return;}flatten(root.left);flatten(root.right);//考慮當前一步做什么 }

這樣，這個題目的基本思路就出來了，那么，我們只需要考慮當前一步需要做什么就可以把這個題目搞定了。

當前一步：由于是后序遍歷，所以順序是左中右，從展開的順序我們可以看出來，明顯是先連接左節點，后連接右節點，所以，我們肯定要先保存右節點的值，然后連接左節點，同時，我們的展開之后，只有右節點，所以，左節點應該設置為null。

經過分析，代碼直接就可以寫出來了。

public?void?flatten(TreeNode?root)?{if(root?==?null){return;}flatten(root.left);flatten(root.right);//考慮當前一步做什么TreeNode?temp?=?root.right;//root.right?=?root.left;//右指針指向左節點root.left?=?null;//左節點值為空while(root.right?!=?null){root?=?root.right;}root.right?=?temp;//最后再將右節點連在右指針后面 }

最終這就是答案了，這不是最佳的答案，但是，這可能是解決二叉樹這種題目的最好的理解方式，同時，非常有助于你理解dfs這種算法的思想。

105. 從前序與中序遍歷序列構造二叉樹

這個題目也是挺不錯的題目，而且其實在我們學習數據結構的時候，這個題目經常會以解答題的方式出現，讓我們考試的時候來做，確實印象深刻，這里，我們看看用代碼怎么解決。

還是同樣的套路，同樣的思路，已經同樣的味道，再來把這道菜炒一下。

首先，確定先序遍歷、中序遍歷還是后序遍歷，既然是由前序遍歷和中序遍歷來推出二叉樹，那么，前序遍歷是更好一些的。

這里我們直接考慮當前一步應該做什么，然后直接做出來這道菜。

當前一步：回想一下以前做這個題目的思路你會發現，我們去構造二叉樹的時候，思路是這樣的，前序遍歷第一個元素肯定是根節點a，那么，當前前序遍歷的元素a，在中序遍歷中，在a這個元素的左邊就是左子樹的元素，在a這個元素右邊的元素就是左子樹的元素，這樣是不是就考慮清楚了當前一步，那么我們唯一要做的就是在中序遍歷數組中找到a這個元素的位置，其他的遞歸來解決即可。

話不多說，看代碼。

public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{//當前前序遍歷的第一個元素int?rootVal?=?preorder[0];root?=?new?TreeNode();root.val?=?rootVal;//獲取在inorder中序遍歷數組中的位置int?index?=?0;for(int?i?=?0;?i?<?inorder.length;?i++){if(rootVal?==?inorder[i]){index?=?i;}}//遞歸去做 }

這一步做好了，后面就是遞歸要做的事情了，讓計算機去工作吧。

public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{//當前前序遍歷的第一個元素int?rootVal?=?preorder[0];root?=?new?TreeNode();root.val?=?rootVal;//獲取在inorder中序遍歷數組中的位置int?index?=?0;for(int?i?=?0;?i?<?inorder.length;?i++){if(rootVal?==?inorder[i]){index?=?i;}}//遞歸去做root.left?=?buildTree(Arrays.copyOfRange(preorder,1,index+1),Arrays.copyOfRange(inorder,0,index));root.right?=?buildTree(Arrays.copyOfRange(preorder,index+1,preorder.length),Arrays.copyOfRange(inorder,index+1,inorder.length));return?root; }

最后，再把邊界條件處理一下，防止root為null的情況出現。

TreeNode?root?=?null;if(preorder.length?==?0){return?root; }

ok，這道菜就這么按照模板炒出來了，相信你，后面的菜你也會抄著炒的。

2 從leetcode的島嶼問題看dfs

1. 步步為營

這一類題目在leetcode還是非常多的，而且在筆試當中你都會經常遇到這種題目，所以，找到解決的方法很重要，其實，最后，你會發現，這類題目，你會了之后就是不再覺得難的題目了。

我們先來看一下題目哈。

題目的意思很簡單，有一個二維數組，里面的數字都是0和1，0代表水域，1代表陸地，讓你計算的是陸地的數量，也就是島嶼的數量。

那么這類題目怎么去解決呢？

其實，我們可以從前面說的從二叉樹看dfs的問題來看這個問題，二叉樹的特征很明顯，就是只有兩個分支可以選擇。

所以，就有了下面的遍歷模板。

//前序遍歷 void?traverse(TreeNode?root)?{System.out.println(root.val);traverse(root.left);traverse(root.right); }

但是，回歸到這個題目的時候，你會發現，我們的整個數據結構是一張二維的圖，如下所示。

當你遍歷這張圖的時候，你會怎么遍歷呢？是不是這樣子？

在（i，j）的位置，是不是可以有四個方向都是可以進行遍歷的，那么是不是這個題目就有了新的解題思路了。

這樣我們就可以把這個的dfs模板代碼寫出來了。

void?dfs(int[][]?grid,?int?i,?int?j)?{//?訪問上、下、左、右四個相鄰方向dfs(grid,?i?-?1,?j);dfs(grid,?i?+?1,?j);dfs(grid,?i,?j?-?1);dfs(grid,?i,?j?+?1); }

你會發現是不是和二叉樹的遍歷很像，只是多了兩個方向而已。

最后還有一個需要考慮的問題就是：base case，其實二叉樹也是需要討論一下base case的，但是，很簡單，當root == null的時候，就是base case。

這里的base case其實也不難，因為這個二維的圖是有邊界的，當dfs的時候發現超出了邊界，是不是就需要判斷了，所以，我們再加上邊界條件。

void?dfs(int[][]?grid,?int?i,?int?j)?{//?判斷?base?caseif?(!inArea(grid,?i,?j))?{return;}//?如果這個格子不是島嶼，直接返回if?(grid[i][j]?!=?1)?{return;}//?訪問上、下、左、右四個相鄰方向dfs(grid,?i?-?1,?j);dfs(grid,?i?+?1,?j);dfs(grid,?i,?j?-?1);dfs(grid,?i,?j?+?1); }//?判斷坐標?(r,?c)?是否在網格中 boolean?inArea(int[][]?grid,?int?i,?int?j)?{return?0?<=?i?&&?i?<?grid.length?&&?0?<=?j?&&?j?<?grid[0].length; }

到這里的話其實這個題目已經差不多完成了，但是，還有一點我們需要注意，當我們訪問了某個節點之后，是需要進行標記的，可以用bool也可以用其他數字標記，不然可能會出現循環遞歸的情況。

所以，最后的解題就出來了。

void?dfs(int[][]?grid,?int?i,?int?j)?{//?判斷?base?caseif?(!inArea(grid,?i,?j))?{return;}//?如果這個格子不是島嶼，直接返回if?(grid[i][j]?!=?1)?{return;}//用2來標記已經遍歷過grid[i][j]?=?2;?//?訪問上、下、左、右四個相鄰方向dfs(grid,?i?-?1,?j);dfs(grid,?i?+?1,?j);dfs(grid,?i,?j?-?1);dfs(grid,?i,?j?+?1); }//?判斷坐標?(r,?c)?是否在網格中 boolean?inArea(int[][]?grid,?int?i,?int?j)?{return?0?<=?i?&&?i?<?grid.length?&&?0?<=?j?&&?j?<?grid[0].length; }

沒有爽夠？再來一題。

2. 再來一發

這個題目跟上面的那題很像，但是這里是求最大的一個島嶼的面積，由于每一個單元格的面積是1，所以，最后的面積就是單元格的數量。

這個題目的解題方法跟上面的那個基本一樣，我們把上面的代碼復制過去，改改就可以了。

class?Solution?{public?int?maxAreaOfIsland(int[][]?grid)?{if(grid?==?null){return?0;}int?max?=?0;for(int?i?=?0;?i?<?grid.length;?i++){for(int?j?=?0;?j?<?grid[0].length;?j++){if(grid[i][j]?==?1){max?=?Math.max(dfs(grid,?i,?j),?max);}}}return?max;}int?dfs(int[][]?grid,?int?i,?int?j)?{//?判斷?base?caseif?(!inArea(grid,?i,?j))?{return?0;}//?如果這個格子不是島嶼，直接返回if?(grid[i][j]?!=?1)?{return?0;}//用2來標記已經遍歷過grid[i][j]?=?2;?//?訪問上、下、左、右四個相鄰方向return?1?+?dfs(grid,?i?-?1,?j)?+?dfs(grid,?i?+?1,?j)?+?dfs(grid,?i,?j?-?1)?+?dfs(grid,?i,?j?+?1);}//?判斷坐標?(r,?c)?是否在網格中boolean?inArea(int[][]?grid,?int?i,?int?j)?{return?0?<=?i?&&?i?<?grid.length?&&?0?<=?j?&&?j?<?grid[0].length;} }

基本思路：?每次進行dfs的時候都對島嶼數量進行+1的操作，然后再求所有島嶼中的最大值。

我們看一下我們代碼的效率如何。

看起來是不是還不錯喲，對的，就是這么搞事情！！！

最后，這篇文章前前后后寫了快一周的時間把，不知道寫的怎么樣，但是，我盡力的把自己所想的表達清楚，主要是一種思路跟解題方法，肯定還有很多其他的方法，去LeetCode去看就明白了。

好了，寫的也夠久了，下篇文章再來看看其他的，希望對大家有幫助，下次再見！！

總結

以上是生活随笔為你收集整理的dfs题目这样去解题，秒杀leetcode题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。