RE4wwu6.jpg

733. 图像渲染

从起始像素向上下左右扩散，只要相邻的点存在并和起始点颜色相同，就染成新的颜色，并继续扩散。

借助一个队列去遍历节点，考察出列的节点，带出满足条件的节点入列。已经染成新色的节点不会入列，避免重复访问节点。

时间复杂度：O(n)O(n)。空间复杂度：O(n)O(n)

const floodFill = (image, sr, sc, newColor) => {
  const row = image.length;
  const column = image[0].length;
  const oldColor = image[sr][sc];

  if (oldColor == newColor) return image;

  const queue = [];

  queue.push([sr, sc])

  while (queue.length) {
    const [i, j] = queue.shift();
    image[i][j] = newColor;

    if (i - 1 >= 0 && image[i - 1][j] == oldColor) queue.push([i - 1, j]);
    if (i + 1 < row && image[i + 1][j] == oldColor) queue.push([i + 1, j]);
    if (j - 1 >= 0 && image[i][j - 1] == oldColor) queue.push([i, j - 1]);
    if (j + 1 < column && image[i][j + 1] == oldColor) queue.push([i, j + 1]);
  }

  return image;
};

695. 岛屿的最大面积

const maxAreaOfIsland = grid => {
  let res = 0;
  // 遍历地图每一个点，找其最大的岛屿
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      res = Math.max(res, dfs(grid, i, j));
    }
  }
  return res;
};

const dfs = (grid, i, j) => {
  // 以下情况不是岛屿，返回0
  if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] !== 1) return 0;

  // 遍历过的点，设置为0
  // 因为后面还会再次遍历到
  grid[i][j] = 0;
  // 该点面积为1
  let area = 1;

  // 从上下左右四方向继续找
  area += dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);

  return area;
};

617. 合并二叉树

var mergeTrees = function(t1, t2) {
    if (t1 === null) {
        return t2
    } else if (t2 === null) {
        return t1
    } else {
        t1.val = t1.val + t2.val
        t1.left = mergeTrees(t1.left, t2.left)
        t1.right = mergeTrees(t1.right, t2.right)
        return t1
    }
};

116. 填充每个节点的下一个右侧节点指针

var connect = function (root) {
    // 边界
    if (root == null) {
        return null;
    }
    const dfs = (root) => {
        // base case
        if (root.left == null && root.right == null) {
            return;
        }
        // 构建右指针
        root.left.next = root.right;
        if (root.next) {
            root.right.next = root.next.left;
        }
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return root;
};