427. 建立四叉树

leetcode 链接

解法一：递归

主要思路就是只考虑最小矩阵，只要当前矩阵有一个坐标的值与别的不同就把当前矩阵分为四个矩阵，然后再递归。

/**
 * // Definition for a QuadTree node.
 * function Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
 *    this.val = val;
 *    this.isLeaf = isLeaf;
 *    this.topLeft = topLeft;
 *    this.topRight = topRight;
 *    this.bottomLeft = bottomLeft;
 *    this.bottomRight = bottomRight;
 * };
 */

/**
 * @param {number[][]} grid
 * @return {Node}
 */
var construct = function (grid) {
  return dfs(grid, grid.length, 0, 0);
};

function dfs(grid, length, x, y) {
  const val = grid[x][y];
  let isChange = false;
  for (let i = x; i < x + length; i++) {
    if (isChange) break;
    for (let j = y; j < y + length; j++) {
      if (grid[i][j] !== val) {
        isChange = true;
        break;
      }
    }
  }
  if (isChange) {
    const mid = length / 2;
    return new Node(
      val,
      0,
      dfs(grid, mid, x, y),
      dfs(grid, mid, x, y + mid),
      dfs(grid, mid, x + mid, y),
      dfs(grid, mid, x + mid, y + mid)
    );
  } else {
    return new Node(val, 1);
  }
}