RE4wwu6.jpg

733. 圖像渲染

從起始像素向上下左右擴(kuò)散，只要相鄰的點(diǎn)存在并和起始點(diǎn)顏色相同，就染成新的顏色，并繼續(xù)擴(kuò)散。

借助一個(gè)隊(duì)列去遍歷節(jié)點(diǎn)，考察出列的節(jié)點(diǎn)，帶出滿足條件的節(jié)點(diǎn)入列。已經(jīng)染成新色的節(jié)點(diǎn)不會(huì)入列，避免重復(fù)訪問節(jié)點(diǎn)。

時(shí)間復(fù)雜度：O(n)O(n)?？臻g復(fù)雜度：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;
  // 遍歷地圖每一個(gè)點(diǎn)，找其最大的島嶼
  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;

  // 遍歷過的點(diǎn)，設(shè)置為0
  // 因?yàn)楹竺孢€會(huì)再次遍歷到
  grid[i][j] = 0;
  // 該點(diǎn)面積為1
  let area = 1;

  // 從上下左右四方向繼續(xù)找
  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. 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

var connect = function (root) {
    // 邊界
    if (root == null) {
        return null;
    }
    const dfs = (root) => {
        // base case
        if (root.left == null && root.right == null) {
            return;
        }
        // 構(gòu)建右指針
        root.left.next = root.right;
        if (root.next) {
            root.right.next = root.next.left;
        }
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return root;
};