DFS与BFS怎么写代码：

1）二叉树的DFS怎么写代码：

1、先左递归、再右递归；
2、遇到叶子节点，（递归触底），直接回溯；
3、当前节点的左递归、右递归函数都调用结束之后，还是要回溯一级；
代码示范：

public static boolean DFSHelper(TreeNode node,...其他参数) {
    TreeNode leftNode = node.left;
    TreeNode rightNode = node.right;
    //...其他代码
    //如果当前节点不是叶子结点：
    if (leftNode != null || rightNode != null) {
        //继续递归该节点的左右子节点：
        methodHelper(leftNode, ...其他参数); //先左递归
        methodHelper(rightNode, ...其他参数); //再右递归
    }
    //如果当前节点是叶子结点：
    else{
        //...其他代码
        // 递归到底了，回溯
        return;
    }
    return;
}

代码示范：DFS深度优先遍历-记录节点路径

/**
* DFS深度优先遍历，寻找某个节点，并记录从根结点到该节点的路径：
* @param root
* @param targetNode 目标节点
* @param deque 记录路径
* @return
*/
public static boolean dfs(TreeNode root, TreeNode targetNode, Deque<TreeNode> deque) {
    //base case
    if (root == null) {
          return false;
    }else{
          deque.push(root);
          if (root == targetNode) {
                return true;
          }
          TreeNode leftNode = root.left; //左子结点
          TreeNode rightNode = root.right; //右子节点
          //非叶子节点
          if (leftNode != null || rightNode != null) {
                //DFS，先左递归，再右递归，然后左递归、右递归都结束之后，回溯一级；
                if (leftNode != null) {
                      boolean b = dfs(leftNode, targetNode, deque);
                      //如果递归过程中，找到了目标节点，则直接返回true，不必再递归其他地方了；
                      if (b) {
                            return b;
                      }
                }
                if (rightNode != null) {
                      boolean b = dfs(rightNode, targetNode, deque);
                      //如果递归过程中，找到了目标节点，则直接返回true，不必再递归其他地方了；
                      if (b) {
                            return b;
                      }
                }
          }
          //叶子结点，直接return，回溯一级：
          //负责记录路径的集合，也要相应撤销选择：
          else{
                deque.pop();
                return false;
          }
    }
    //左递归、右递归都结束之后，回溯一级；
    //负责记录路径的集合，也要相应撤销选择：
    deque.pop();
    return false;
}

2）非树结构的DFS怎么写代码：

非树结构的DFS与二叉树的DFS原理是一样的，唯一不同的是二叉树的DFS涉及到对左子树的左递归和右子树的右递归，而非树结构没有子树的概念，
所以非树结构是直接递归下一级元素，递归触底之后直接回溯一级，以及每一个递归函数调用结束之后，都要回溯一级。

代码流程：
1、先递归遍历该元素的下一级；
2、如果遇到最后一个元素，（递归触底），直接回溯；
3、当前元素的递归函数调用结束之后，也是记得要回溯一级；

代码示例：全排列问题：

/**
* 全排列问题：
* 思路：把nums中的每个元素，抽象成以该节点为根节点的多叉树，DFS该多叉树，记录路径
* 最终所有的路径的组合就是result；
*
* @param nums
* @return
*/
public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    for (int root : nums) {
        list.clear();
        list.add(root);
        dfs(root, nums, list, result);
    }
    System.out.println("result = " + result);
    return result;
}

dfs：全排列问题——非树结构

/**
* 将数组中每个元素抽象为：以其为根节点的多叉树，当然这里没有子树的概念
* DFS深度优先遍历以数组中每个元素为根节点的多叉树，记录路径；
* @param deque
*/
public static void dfs(int root, int[] nums, LinkedList<Integer> deque, List<List<Integer>> result) {
    for (int num : nums) {
          if (num == root) {
                continue;
          }
          if (!deque.contains(num)) {
                deque.add(num);
                //如果是最后一个元素，递归触底，然后"路径记录"回溯一级：
                if (deque.size() == nums.length) {
                      //递归已经触底，将其记录下来：
                      result.add(new LinkedList<>(deque));
                      deque.pollLast(); //"路径记录"回溯一级
                      return;
                }
                //如果没有触底，当前元素的递归函数调用结束之后，也是要记得将"路径记录"回溯一级；
                else {
                      dfs(root, nums, deque, result);
                      //递归结束之后，"路径记录"回溯一级；
                      deque.pollLast(); 
                }
          } else {
                continue;
          }
    }
    return;
}

3）二叉树的BFS怎么写代码：

• BFS函数的声明中，用一个队列参数作为辅助数据结构；
• 先将队列中的节点出队列，然后从左到右将该节点的子节点都加入到队列，
• 直到队列为空；

代码示例：

public static void BFSHelper(Queue<TreeNode> queue,其他参数) {
    while (!queue.isEmpty()) {
          TreeNode headNode = queue.poll(); //头结点
          TreeNode leftNode = headNode.left;
          TreeNode rightNode = headNode.right;
          //如果为非叶子节点：
          if (leftNode != null) {
             queue.offer(leftNode);
          }else if(rightNode != null){
             queue.offer(rightNode);
          }
          //如果为叶子结点:
          else{
             continue;
          }
    }
    return;
}