DFS：从勉强看懂到运用自如

恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

前言

在笔者大大小小笔试了五六场之后，似乎得到了一点规律，互联网大厂的笔试题集中在两大块，一是dp动态规划，另外一个就是dfs深度优先搜索（也包含回溯问题）了。之前笔试的时候，总是觉得面对这种类型的题目，即使勉强写出来了，也远远没有达到融会贯通的程度，很是苦恼。看了几十篇高赞高评论的总结对比文章后，并没有觉得有什么帮助，我总结了两个原因，第一个原因就是作者讲的太浅了，最然容易理解，却无法实际运用到更加复杂的场景中，另一个原因就是，很多别人得出的宝贵结论，你因为缺少自己的思考和大量题目的训练而无法感同身受，因而无法体会到其中的精妙之处。所以，我最后总结出的解决dfs的最好方法是我要打十个！！！： 做 出 l e e t c o d e 问 题 中 d f s 专 项 下 面 的 所 有 题 目 ！ 做出leetcode问题中dfs专项下面的所有题目！ 做出leetcode问题中dfs专项下面的所有题目！ （咋感觉比打十个还猖狂。。orz）

正文

以下是关于dfs的所有中等难度题目，一共 给大家感受一下题量，剩下的就不粘了，完整版可以看这里。所以这也告诉我们，题目是千变万化的，只有具备解出dfs题目的能力才是关键。然鹅！！这里一共有90道左右，我。。。后悔了。。。但但是！！规律我一定要找到，总结给大家，前提是你能像我一样自己绞尽脑汁、花了大量时间在上面钻研，你才能有所感悟。

1. 路径和问题

(代码已详细注释，注释很细节，是引导思维的)

//Given a binary tree and a sum, find all root-to-leaf paths where each path's s
//um equals the given sum. 
//
// Note: A leaf is a node with no children. 
//
// Example: 
//
// Given the below binary tree and sum = 22, 
//
// 
//      5
//     / \
//    4   8
//   /   / \
//  11  13  4
// /  \    / \
//7    2  5   1
// 
//
// Return: 
//
// 
//[
//   [5,4,11,2],
//   [5,8,4,5]
//]


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	//这里为什么写在方法外呢？这样可以作为一个类方法共同使用，简化代码。
    List res = new LinkedList();
    public List pathSum(TreeNode root, int sum) {
    	//为什么要重新写个函数呢？
    	//因为回溯的关键是有记忆的，除了栈，还有的就是参数传递，主函数的参数不适合递归。
        dfs(root,new LinkedList(),sum);//也可以用ArrayList
        return res;
    }

    private void dfs(TreeNode node,LinkedList temp,int target){
        if(node==null) {
            return;
        }
        temp.add(node.val);
        if(node.left==null && node.right==null && node.val == target) {
            res.add(new LinkedList(temp));
        }
        //以上都是递归出口（判断条件），可以理解为dfs中我走到头了，
        //发现对或者不对，我标记之后，都要回退一步。
        //下面两句就是常规情况，发现还没到递归出口，我深入往前探进，
        //同时用栈存了我之前的位置，并用参数传递给下一步我已经存储的信息。
        dfs(node.left,temp,target-node.val);
        dfs(node.right,temp,target-node.val);
        //注意下面这句是带着上面递归出口共用的
        temp.removeLast();
    }
}
temp的变化过程（从上至下）：
				5 
				5 4 
				5 4 11 
				5 4 11 7 //到这满了，下一个为null，到达叶子节点
				=============
				5 4 11 7 //有两次是因为两次打印了两次，和上一次可以只看作一次
				5 4 11 
				5 4 11 2 
				=============
				5 4 11 2 
				5 4 11 
				=============
				5 4 11 
				5 4 
				=============
				5 4 
				5 
				5 8 
				5 8 13 
				=============
				5 8 13 
				5 8 
				5 8 4 
				5 8 4 5 
				=============
				5 8 4 5 
				5 8 4 
				5 8 4 1 
				=============
				5 8 4 1 
				5 8 4 
				=============
				5 8 4 
				5 8 
				=============
				5 8 
				5 
				=============
				5  

2.打印二叉树为链表

//Given a binary tree, flatten it to a linked list in-place. 
//
// For example, given the following tree: 
//
// 
//    1
//   / \
//  2   5
// / \   \
//3   4   6
// 
//
// The flattened tree should look like: 
//
// 
//1
// \
//  2
//   \
//    3
//     \
//      4
//       \
//        5
//         \
//          6
// 



//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre = null;
    public void flatten(TreeNode root) {
        if(root==null) return; 
        flatten(root.right); //后序串接
        flatten(root.left);	//先一口气遍历到最靠右的叶子节点，再往回拼接
        root.right = pre;//以下三句，拼接串，此时的pre实际是上次弹栈之前保存的节点值。
        root.left = null;
        pre = root;
    }
}

3.二叉树打印层链表

//You are given a perfect binary tree where all leaves are on the same level, an
//d every parent has two children. The binary tree has the following definition: 
//
// 
//struct Node {
//  int val;
//  Node *left;
//  Node *right;
//  Node *next;
//}
// 
//
// Populate each next pointer to point to its next right node. If there is no ne
//xt right node, the next pointer should be set to NULL. 
//
// Initially, all next pointers are set to NULL. 
//
// 
//
// Follow up: 
//
// 
// You may only use constant extra space. 
// Recursive approach is fine, you may assume implicit stack space does not coun
//t as extra space for this problem. 
// 
//
// 
// Example 1: 
//
// 
//
// 
//Input: root = [1,2,3,4,5,6,7]
//Output: [1,#,2,3,#,4,5,6,7,#]
//Explanation: Given the above perfect binary tree (Figure A), your function sho
//uld populate each next pointer to point to its next right node, just like in Fig
//ure B. The serialized output is in level order as connected by the next pointers
//, with '#' signifying the end of each level.
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the given tree is less than 4096. 
// -1000 3 which represents the number 123. 
//
//
// Find the total sum of all root-to-leaf numbers. 
//
// Note: A leaf is a node with no children. 
//
// Example: 
//
// 
//Input: [1,2,3]
//    1
//   / \
//  2   3
//Output: 25
//Explanation:
//The root-to-leaf path 1->2 represents the number 12.
//The root-to-leaf path 1->3 represents the number 13.
//Therefore, sum = 12 + 13 = 25. 
//
// Example 2: 
//
// 
//Input: [4,9,0,5,1]
//    4
//   / \
//  9   0
// / \
//5   1
//Output: 1026
//Explanation:
//The root-to-leaf path 4->9->5 represents the number 495.
//The root-to-leaf path 4->9->1 represents the number 491.
//The root-to-leaf path 4->0 represents the number 40.
//Therefore, sum = 495 + 491 + 40 = 1026. 


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
import java.lang.*;
class Solution {
    List arr = new ArrayList();
    public int sumNumbers(TreeNode root) {
        dfs(root,new StringBuilder(""));
        int sum = 0;
        for(StringBuilder e:arr){
            sum+=Integer.parseInt(e.toString());
        }
        return sum;
    }
    private void dfs(TreeNode node, StringBuilder num){
        if(node==null) return;
        num.append(node.val);
        //唯一的变化就是这里出口条件变了一下，是不是慢慢有了套路的感觉？
        if(node.left==null && node.right==null){ 
            arr.add(new StringBuilder(num));
        }
        dfs(node.left,num);
        dfs(node.right,num);
        num = num.deleteCharAt(num.length()-1);
    }

}

5. 图的深拷贝

有时候做到这里，部分同学的畏难心理就发作了，关于图的题目都不做，实际上，关于图的算法在面试中也是有一定比例考察的，所以最好拿下几个比较经典的题目。这道题目表面上是图的题目，实际就是二叉树的变体而已（可以认为二叉树是一种特殊的图）。

//Given a reference of a node in a connected undirected graph. 
//
// Return a deep copy (clone) of the graph. 
//
// Each node in the graph contains a val (int) and a list (List[Node]) of its ne
//ighbors. 
//
// 
//class Node {
//    public int val;
//    public List neighbors;
//}
// 
//
// 
//
// Test case format: 
//
// For simplicity sake, each node's value is the same as the node's index (1-ind
//exed). For example, the first node with val = 1, the second node with val = 2, a
//nd so on. The graph is represented in the test case using an adjacency list. 
//
// Adjacency list is a collection of unordered lists used to represent a finite 
//graph. Each list describes the set of neighbors of a node in the graph. 
//
// The given node will always be the first node with val = 1. You must return th
//e copy of the given node as a reference to the cloned graph. 
//
// 
// Example 1: 
//
// 
//Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
//Output: [[2,4],[1,3],[2,4],[1,3]]
//Explanation: There are 4 nodes in the graph.
//1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
//2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
//3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
//4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
// 
//
// Example 2: 
//
// 
//Input: adjList = [[]]
//Output: [[]]
//Explanation: Note that the input contains one empty list. The graph consists o
//f only one node with val = 1 and it does not have any neighbors.
// 
//
// Example 3: 
//
// 
//Input: adjList = []
//Output: []
//Explanation: This an empty graph, it does not have any nodes.
// 
//
// Example 4: 
//
// 
//Input: adjList = [[2],[1]]
//Output: [[2],[1]]
// 
//
// 
// Constraints: 
//
// 
// 1