點(diǎn)個(gè)贊，看一看住册，好習(xí)慣婶博！本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收錄，這是我花了 3 個(gè)月總結(jié)的一線大廠 Java 面試總結(jié)荧飞，本人已拿大廠 offer凡蜻。
另外，原創(chuàng)文章首發(fā)在我的個(gè)人博客：blog.ouyangsihai.cn垢箕，歡迎訪問(wèn)划栓。

今天來(lái)聊聊 dfs 的解題方法，這些方法都是總結(jié)之后的出來(lái)的經(jīng)驗(yàn)条获，有值得借鑒的地方忠荞。

1 從二叉樹(shù)看 dfs

二叉樹(shù)的思想其實(shí)很簡(jiǎn)單，我們剛剛開(kāi)始學(xué)習(xí)二叉樹(shù)的時(shí)候帅掘，在做二叉樹(shù)遍歷的時(shí)候是不是最常見(jiàn)的方法就是遞歸遍歷委煤，其實(shí)，你會(huì)發(fā)現(xiàn)修档，二叉樹(shù)的題目的解題方法基本上都是遞歸來(lái)解題碧绞，我們只需要走一步，其他的由遞歸來(lái)做吱窝。

我們先來(lái)看一下二叉樹(shù)的前序遍歷讥邻、中序遍歷、后序遍歷的遞歸版本院峡。

//前序遍歷
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);
}

//后續(xù)遍歷
void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    System.out.println(root.val);
}

其實(shí)你會(huì)發(fā)現(xiàn)兴使，二叉樹(shù)的遍歷的過(guò)程就能夠看出二叉樹(shù)遍歷的一個(gè)整體的框架，其實(shí)這個(gè)也是二叉樹(shù)的解題的整體的框架就是下面這樣的照激。

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

我們?cè)诮忸}的時(shí)候励幼，我們只需要去想當(dāng)前的操作應(yīng)該怎么實(shí)現(xiàn)汰寓，后面的由遞歸去實(shí)現(xiàn)，至于用前序中序還是后序遍歷苹粟，由具體的情況來(lái)實(shí)現(xiàn)有滑。

下面來(lái)幾個(gè)二叉樹(shù)的熱身題，來(lái)體會(huì)一下這種解題方法六水。

另外俺孙，這些知識(shí)的話辣卒，我都寫了原創(chuàng)文章掷贾，比較系統(tǒng)的講解了，大家可以看看荣茫，會(huì)有一定得收獲的想帅。

1. 如何把?叉樹(shù)所有的節(jié)點(diǎn)中的值加?

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

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

接下來(lái)浅缸，考慮當(dāng)前的一步需要做什么事情，在這里魄咕，當(dāng)然是給當(dāng)前的節(jié)點(diǎn)加一衩椒。

void traverse(TreeNode root) {
    if(root == null) {
        return;
    }
    //這里改為給當(dāng)前的節(jié)點(diǎn)加一。
    root.val += 1;
    traverse(root.left);
    traverse(root.right);
}

發(fā)現(xiàn)是不是水到渠成哮兰？

不爽毛萌？再來(lái)一個(gè)簡(jiǎn)單的。

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

這個(gè)問(wèn)題我們直接考慮當(dāng)前一步需要做什么喝滞，也就是什么情況阁将，這是同一顆二叉樹(shù)？

1）兩棵樹(shù)的當(dāng)前節(jié)點(diǎn)等于空：root1 == null && root2 == null右遭，這個(gè)時(shí)候返回 true做盅。
2）兩棵樹(shù)的當(dāng)前節(jié)點(diǎn)任意一個(gè)節(jié)點(diǎn)為空：root1 == null || root2 == null，這個(gè)時(shí)候當(dāng)然是 false窘哈。
3）兩棵樹(shù)的當(dāng)前節(jié)點(diǎn)都不為空言蛇，但是 val 不一樣：root1.val != root2.val，返回 false宵距。

所以腊尚，答案就顯而易見(jiàn)了。

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

有了上面的講解劝篷，我相信你已經(jīng)有了基本的思路了，下面我們來(lái)點(diǎn)有難度的題目民宿，小試牛刀娇妓。

3. leetcode中等難度解析

114. 二叉樹(shù)展開(kāi)為鏈表

這個(gè)題目是二叉樹(shù)中的中等難度題目，但是通過(guò)率很低活鹰，那么我們用上面的思路來(lái)看看是否可以輕松解決這個(gè)題目哈恰。

這個(gè)題目乍一看，根據(jù)前面的思路志群，你可以能首先會(huì)選擇前序遍歷的方式來(lái)解決着绷，是可以的，但是锌云，比較麻煩荠医，因?yàn)榍靶虮闅v的方式會(huì)改變右節(jié)點(diǎn)的指向，導(dǎo)致比較麻煩桑涎，那么彬向，如果前序遍歷不行，就考慮中序和后序遍歷了攻冷，由于娃胆，在展開(kāi)的時(shí)候，只需要去改變左右節(jié)點(diǎn)的指向等曼，所以里烦，這里其實(shí)最好的方式還是用后續(xù)遍歷，既然是后續(xù)遍歷涉兽，那么我們就可以快速的把后續(xù)遍歷的框架寫出來(lái)了招驴。

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

這樣，這個(gè)題目的基本思路就出來(lái)了枷畏，那么别厘，我們只需要考慮當(dāng)前一步需要做什么就可以把這個(gè)題目搞定了。

當(dāng)前一步：由于是后序遍歷拥诡，所以順序是左右中触趴，從展開(kāi)的順序我們可以看出來(lái)，明顯是先連接左節(jié)點(diǎn)渴肉，后連接右節(jié)點(diǎn)冗懦，所以，我們肯定要先保存右節(jié)點(diǎn)的值仇祭，然后連接左節(jié)點(diǎn)披蕉，同時(shí)，我們的展開(kāi)之后，只有右節(jié)點(diǎn)没讲，所以眯娱，左節(jié)點(diǎn)應(yīng)該設(shè)置為null。

經(jīng)過(guò)分析爬凑，代碼直接就可以寫出來(lái)了徙缴。

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

最終這就是答案了，這不是最佳的答案嘁信，但是于样，這可能是解決二叉樹(shù)這種題目的最好的理解方式，同時(shí)潘靖，非常有助于你理解dfs這種算法的思想穿剖。

105. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)

這個(gè)題目也是挺不錯(cuò)的題目，而且其實(shí)在我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候秘豹，這個(gè)題目經(jīng)常會(huì)以解答題的方式出現(xiàn)携御，讓我們考試的時(shí)候來(lái)做昌粤，確實(shí)印象深刻既绕，這里，我們看看用代碼怎么解決涮坐。

還是同樣的套路凄贩，同樣的思路，已經(jīng)同樣的味道袱讹，再來(lái)把這道菜炒一下疲扎。

首先，確定先序遍歷捷雕、中序遍歷還是后序遍歷椒丧，既然是由前序遍歷和中序遍歷來(lái)推出二叉樹(shù)，那么救巷，前序遍歷是更好一些的壶熏。

這里我們直接考慮當(dāng)前一步應(yīng)該做什么，然后直接做出來(lái)這道菜浦译。

當(dāng)前一步：回想一下以前做這個(gè)題目的思路你會(huì)發(fā)現(xiàn)棒假，我們?nèi)?gòu)造二叉樹(shù)的時(shí)候，思路是這樣的精盅，前序遍歷第一個(gè)元素肯定是根節(jié)點(diǎn)a帽哑，那么，當(dāng)前前序遍歷的元素a叹俏，在中序遍歷中妻枕，在a這個(gè)元素的左邊就是左子樹(shù)的元素，在a這個(gè)元素右邊的元素就是左子樹(shù)的元素，這樣是不是就考慮清楚了當(dāng)前一步屡谐，那么我們唯一要做的就是在中序遍歷數(shù)組中找到a這個(gè)元素的位置鹰贵，其他的遞歸來(lái)解決即可。

話不多說(shuō)康嘉，看代碼碉输。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    //當(dāng)前前序遍歷的第一個(gè)元素
    int rootVal = preorder[0];
    root = new TreeNode();
    root.val = rootVal;

    //獲取在inorder中序遍歷數(shù)組中的位置
    int index = 0;
    for(int i = 0; i < inorder.length; i++){
        if(rootVal == inorder[i]){
            index = i;
        }
    }

    //遞歸去做
}

這一步做好了，后面就是遞歸要做的事情了亭珍，讓計(jì)算機(jī)去工作吧敷钾。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    //當(dāng)前前序遍歷的第一個(gè)元素
    int rootVal = preorder[0];
    root = new TreeNode();
    root.val = rootVal;

    //獲取在inorder中序遍歷數(shù)組中的位置
    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的情況出現(xiàn)阻荒。

TreeNode root = null;

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

ok，這道菜就這么按照模板炒出來(lái)了众羡，相信你侨赡，后面的菜你也會(huì)抄著炒的。

2 從leetcode的島嶼問(wèn)題看dfs

1. 步步為營(yíng)

這一類題目在leetcode還是非常多的粱侣，而且在筆試當(dāng)中你都會(huì)經(jīng)常遇到這種題目羊壹，所以，找到解決的方法很重要齐婴，其實(shí)油猫，最后，你會(huì)發(fā)現(xiàn)柠偶，這類題目情妖，你會(huì)了之后就是不再覺(jué)得難的題目了。

我們先來(lái)看一下題目哈诱担。

題目的意思很簡(jiǎn)單毡证，有一個(gè)二維數(shù)組，里面的數(shù)字都是0和1蔫仙，0代表水域料睛，1代表陸地，讓你計(jì)算的是陸地的數(shù)量匀哄，也就是島嶼的數(shù)量秦效。

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

其實(shí)涎嚼，我們可以從前面說(shuō)的從二叉樹(shù)看dfs的問(wèn)題來(lái)看這個(gè)問(wèn)題阱州，二叉樹(shù)的特征很明顯，就是只有兩個(gè)分支可以選擇法梯。

所以苔货，就有了下面的遍歷模板犀概。

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

但是，回歸到這個(gè)題目的時(shí)候夜惭，你會(huì)發(fā)現(xiàn)姻灶，我們的整個(gè)數(shù)據(jù)結(jié)構(gòu)是一張二維的圖，如下所示诈茧。

當(dāng)你遍歷這張圖的時(shí)候产喉，你會(huì)怎么遍歷呢？是不是這樣子敢会？

在（i曾沈，j）的位置，是不是可以有四個(gè)方向都是可以進(jìn)行遍歷的鸥昏，那么是不是這個(gè)題目就有了新的解題思路了塞俱。

這樣我們就可以把這個(gè)的dfs模板代碼寫出來(lái)了。

void dfs(int[][] grid, int i, int j) {
    // 訪問(wèn)上吏垮、下障涯、左、右四個(gè)相鄰方向
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}

你會(huì)發(fā)現(xiàn)是不是和二叉樹(shù)的遍歷很像膳汪，只是多了兩個(gè)方向而已唯蝶。

最后還有一個(gè)需要考慮的問(wèn)題就是：base case，其實(shí)二叉樹(shù)也是需要討論一下base case的旅敷，但是生棍，很簡(jiǎn)單颤霎，當(dāng)root == null的時(shí)候媳谁，就是base case。

這里的base case其實(shí)也不難友酱，因?yàn)檫@個(gè)二維的圖是有邊界的晴音，當(dāng)dfs的時(shí)候發(fā)現(xiàn)超出了邊界，是不是就需要判斷了缔杉，所以锤躁，我們?cè)偌由线吔鐥l件。

void dfs(int[][] grid, int i, int j) {
    // 判斷 base case
    if (!inArea(grid, i, j)) {
        return;
    }
    // 如果這個(gè)格子不是島嶼或详，直接返回
    if (grid[i][j] != 1) {
        return;
    }
    
    // 訪問(wèn)上系羞、下、左霸琴、右四個(gè)相鄰方向
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}

// 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
boolean inArea(int[][] grid, int i, int j) {
    return 0 <= i && i < grid.length 
            && 0 <= j && j < grid[0].length;
}

到這里的話其實(shí)這個(gè)題目已經(jīng)差不多完成了椒振，但是，還有一點(diǎn)我們需要注意梧乘，當(dāng)我們?cè)L問(wèn)了某個(gè)節(jié)點(diǎn)之后澎迎，是需要進(jìn)行標(biāo)記的庐杨，可以用bool也可以用其他數(shù)字標(biāo)記，不然可能會(huì)出現(xiàn)循環(huán)遞歸的情況夹供。

所以灵份，最后的解題就出來(lái)了。

void dfs(int[][] grid, int i, int j) {
    // 判斷 base case
    if (!inArea(grid, i, j)) {
        return;
    }
    // 如果這個(gè)格子不是島嶼哮洽，直接返回
    if (grid[i][j] != 1) {
        return;
    }

    //用2來(lái)標(biāo)記已經(jīng)遍歷過(guò)
    grid[i][j] = 2; 
    
    // 訪問(wèn)上填渠、下、左鸟辅、右四個(gè)相鄰方向
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}

// 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
boolean inArea(int[][] grid, int i, int j) {
    return 0 <= i && i < grid.length 
            && 0 <= j && j < grid[0].length;
}

沒(méi)有爽夠揭蜒？再來(lái)一題。

2. 再來(lái)一發(fā)

這個(gè)題目跟上面的那題很像剔桨，但是這里是求最大的一個(gè)島嶼的面積屉更，由于每一個(gè)單元格的面積是1，所以洒缀，最后的面積就是單元格的數(shù)量瑰谜。

這個(gè)題目的解題方法跟上面的那個(gè)基本一樣，我們把上面的代碼復(fù)制過(guò)去树绩，改改就可以了萨脑。

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 case
        if (!inArea(grid, i, j)) {
            return 0;
        }
        // 如果這個(gè)格子不是島嶼，直接返回
        if (grid[i][j] != 1) {
            return 0;
        }

        //用2來(lái)標(biāo)記已經(jīng)遍歷過(guò)
        grid[i][j] = 2; 
        
        // 訪問(wèn)上饺饭、下渤早、左、右四個(gè)相鄰方向
        return 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
    }

    // 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
    boolean inArea(int[][] grid, int i, int j) {
        return 0 <= i && i < grid.length 
                && 0 <= j && j < grid[0].length;
    }
}

基本思路： 每次進(jìn)行dfs的時(shí)候都對(duì)島嶼數(shù)量進(jìn)行+1的操作瘫俊，然后再求所有島嶼中的最大值鹊杖。

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

看起來(lái)是不是還不錯(cuò)喲扛芽，對(duì)的骂蓖，就是這么搞事情！４狻登下！

最后，這篇文章前前后后寫了快一周的時(shí)間把叮喳，不知道寫的怎么樣被芳，但是，我盡力的把自己所想的表達(dá)清楚馍悟，主要是一種思路跟解題方法畔濒，肯定還有很多其他的方法，去LeetCode去看就明白了赋朦。

好了篓冲，寫的也夠久了李破，下篇文章再來(lái)看看其他的，希望對(duì)大家有幫助壹将，再次再見(jiàn)｀凸ァ！

最后诽俯，再分享我歷時(shí)三個(gè)月總結(jié)的 Java 面試 + Java 后端技術(shù)學(xué)習(xí)指南妇菱，這是本人這幾年及春招的總結(jié)，已經(jīng)拿到了大廠 offer暴区，整理成了一本電子書闯团，拿去不謝，目錄如下：

現(xiàn)在免費(fèi)分享大家仙粱，在下面我的公眾號(hào) 程序員的技術(shù)圈子 回復(fù) 面試 即可獲取房交。