[[]]的套路

模板

  1. let marksSet = new Set
  2. function dfs(i,j){
  3.   // 如果i越界或者j越界就结束
  4.   if(i>arr[1].length||j>arr.length) return
  5.   // 如果访问过就算了
  6.   if(marksSet.has(`${i}-${j}`)) return
  7.   // marksSet 存储标记我来过了
  8.   marksSet.add(`${i}-${j}`)
  9.   return  dfs(i + 1, j)+
  10.   dfs(i, j+1)+
  11.   dfs(i-1, j)+
  12.   dfs(i, j-1)+1
  13.   // 有特殊情况也可以 marksSet.delete(`${i}-${j}`)
  14. }
  15. // 单点入口
  16. dfs(0,0)
  17. // 多点入口
  18. for(let j in arr){
  19.     for(let k in arr[j]){
  20.       dfs(j,k)
  21.   }
  22. }

上面用到了Set缓存，有些时候不用单独存，只需要原地缓存就好。也就是直接将当前值变为一个特定值，只要等于特定值就说明缓存了。

  1. function dfs(i,j){
  2.   // 如果i越界或者j越界就结束
  3.   if(i>arr.length||j>arr[0].length||i<0||j<0||arr[i][j]==-1) return
  4.   arr[i][j] = -1
  5.   return  dfs(i + 1, j)+
  6.   dfs(i, j+1)+
  7.   dfs(i-1, j)+
  8.   dfs(i, j-1)+1
  9.   // 有特殊情况也可以 marksSet.delete(`${i}-${j}`)
  10. }

例题

463岛屿周长、 石子问题

树的DFS

  1. if (!root) return 0;
  2. dfs(root)
  3. function dfs(root){
  4.   // 有时候需要存储个状态，一般不用，直接往下突就完事了
  5.   if(root){
  6.      // dosomething
  7.   }
  8.     dfs(root.left)
  9.   dfs(root.right)
  10. }

例题

129求根到叶子节点数字之和