从三道leetcode掌握深度优先搜索（DFS）

const F = (n) => {
  // 小问题直接解决
  if (n === 0) return 0
  if (n === 1) return 1
  // 把大问题化解为小问题
  // 我们只需要将问题分解为小问题F(n - 1)和F(n - 2)
  // 不用关心F(n - 1)和F(n -2)的求解过程
  // 事实上只要n-1和n-2大于1就会一直拆解问题
  // 直到遇到已经的0和1的解
  return F(n - 1) + F(n - 2) 
}
复制代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  const ans = []
  if (!root) return ans
  // 实现DFS
  const dfs = (node) => {
    // 在搜索过程中往答案中加入当前节点值
    ans.push(node.val)
    // 递归的出口为当前节点没有左子节点和右子节点
    // 递归搜索左子节点
    if (node.left) {
      dfs(node.left)
    }
    // 递归搜索右子节点
    if (node.right) {
      dfs(node.right)
    }
  }
  dfs(root)
  return ans
};
复制代码

var mergeTrees = function(root1, root2) {
  // 递归的一个重要逻辑就是要定义出口防止无限递归
  // 下面的条件判断可以理解为出口
  // 需要注意的是，出口可能是解
  // 或者是不符条件的终止，我们将不符条件的终止叫做剪枝
  if (!root1 && !root2) {
    return null
  }
  if (root1 && !root2) {
    return root1
  }
  if (!root1 && root2) {
    return root2
  }
  // 如果问题还没被分解为最小问题
  // 则需要再次分解成子问题
  // 子问题的求解顺序则决定我们是使用DFS还是BFS
  const node = new TreeNode(root1.val + root2.val)
  // 我们在这先求解node.left
  // 也就是会对root1.left和root2.left进行合并
  // 当root1.left和root2.left仍然不是最小子问题时会继续往下递归调用mergeTrees
  // 所以这是一种持续深入的递归求解模式，我们称其为DFS
  node.left = mergeTrees(root1.left, root2.left)
  // 当执行到右子节点时，左子节点及左子节点的后代实际都已经完成合并
  node.right = mergeTrees(root1.right, root2.right)
  return node;
};
复制代码

var maxAreaOfIsland = function(grid) {
  // 初始化m/n用于计算边界
  const m = grid.length
  const n = grid[0].length
  // 初始答案0
  let ans = 0
  // dfs函数
  const getGrid = (row, col) => {
    let count = 0
    // 出口条件当前格子为0
    if (grid[row][col] === 1) {
      // 这边可以重点注意下
      // 搜索过的格子置为0防止重复搜索
      grid[row][col] = 0
      count++
      // 先搜索某一方向
      // 直到遇到出口为止
      // 所以当前搜索模式为深度优先搜索DFS
      if (row > 0) {
        count += getGrid(row - 1, col)
      }
      if (row + 1 < m) {
        count += getGrid(row + 1, col)
      }
      if (col > 0) {
        count += getGrid(row, col - 1)
      }
      if (col + 1 < n) {
        count += getGrid(row, col + 1)
      }
    }
    return count
  }
  // 不同于于树结构有根节点
  // 对于二维数组来说没有根节点
  // 所以我们需要遍历使用每个节点来进行上下左右的搜索
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        // 搜索更新最大值
        ans = Math.max(getGrid(i, j), ans)
      }
    }
  }
  return ans
};
复制代码