617. 合并二叉树

1. DFS + 递归

  1. var mergeTrees = function (root1, root2) {
  2.   if (root1 && root2) {
  3.     root1.val += root2.val;
  4.     root1.left = mergeTrees(root1.left, root2.left); // 处理左边的树
  5.     root1.right = mergeTrees(root1.right, root2.right); // 处理右边的树
  6.   }
  7.   return root1 || root2;
  8. };

可以从 “归” 开始回看。

  • return root1 || root2;

    • 只要 root1 一开始不是空，那么，最后一次 return 时，会将 root1 返回

687. 最长同值路径

方法1 - DFS

  1. var longestUnivaluePath = function (root) {
  2.   let ans = 0;
  4.   const dfs = (root) => {
  5.     if (root === null) return 0;
  6.     const left = dfs(root.left), right = dfs(root.right);
  7.     let l = 0, r = 0;
  8.     if (root.left && root.left.val === root.val) l = left + 1;
  9.     if (root.right && root.right.val === root.val) r = right + 1;
  10.     ans = Math.max(ans, l + r);
  11.     return Math.max(l, r);
  12.   }
  14.   dfs(root);
  15.   return ans;
  16. };

幻灯片语法不支持。

695. 岛屿的最大面积

1. DFS + 递归

  1. var maxAreaOfIsland = function (grid) {
  2.   // 递归，遍历与当前陆地相连的所有陆地
  3.   const dfs = (grid, i, j) => {
  4.     if (i < 0 || j < 0 || i > totalRowNum - 1 || j > totalColNum - 1) return 0; // 越界
  5.     if (grid[i][j] !== 1) return 0; // 不是陆地
  6.     // 这个点是陆地
  7.     grid[i][j] = 0; // 将遍历过的陆地全部置 0，防止重复遍历
  8.     return 1 + // 1 表示当前这个点是陆地
  9.       dfs(grid, i - 1, j) + // 上
  10.       dfs(grid, i + 1, j) + // 下
  11.       dfs(grid, i, j - 1) + // 左
  12.       dfs(grid, i, j + 1); // 右
  13.   }
  15.   let result = 0; // 最终结果
  16.   // 遍历 grid
  17.   const totalRowNum = grid.length, // 总行数
  18.     totalColNum = grid[0].length; // 总列数
  19.   for (let i = 0; i < totalRowNum; i++) { // 遍历行
  20.     for (let j = 0; j < totalColNum; j++) { // 遍历列
  21.       result = Math.max(result, dfs(grid, i, j));
  22.     }
  23.   }
  24.   return result;
  25. };

  • 如何防止同一个陆地被重复遍历？

    • 但凡是遍历过的陆地（也就是被计数过的陆地），就将其重置为 0；重置以后，下次再遍历到它时，它将不再被识别为陆地。