427.建立四叉树.md

427.建立四叉树

/*
 * @lc app=leetcode.cn id=427 lang=typescript
 *
 * [427] 建立四叉树
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: boolean
 *     isLeaf: boolean
 *     topLeft: Node | null
 *     topRight: Node | null
 *     bottomLeft: Node | null
 *     bottomRight: Node | null
 *     constructor(val?: boolean, isLeaf?: boolean, topLeft?: Node, topRight?: Node, bottomLeft?: Node, bottomRight?: Node) {
 *         this.val = (val===undefined ? false : val)
 *         this.isLeaf = (isLeaf===undefined ? false : isLeaf)
 *         this.topLeft = (topLeft===undefined ? null : topLeft)
 *         this.topRight = (topRight===undefined ? null : topRight)
 *         this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
 *         this.bottomRight = (bottomRight===undefined ? null : bottomRight)
 *     }
 * }
 */
function construct(grid: number[][]): Node | null {}

// @lc code=end

解法 1: 前缀和

function construct(grid: number[][]): Node | null {
  const n = grid.length
  const sum: number[][] = Array.from({ length: n }, () => new Array(n).fill(0))
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      sum[i][j] = (sum[i - 1]?.[j] ?? 0) + (sum[i][j - 1] ?? 0) - (sum[i - 1]?.[j - 1] ?? 0) + grid[i][j]
    }
  }

  const dfs = (start: [number, number], end: [number, number]) => {
    const node = new Node(),
      [x1, y1] = start,
      [x2, y2] = end
    const s = sum[x2][y2] - (sum[x1 - 1]?.[y2] ?? 0) - (sum[x2][y1 - 1] ?? 0) + (sum[x1 - 1]?.[y1 - 1] ?? 0)
    if (s === 0) {
      node.val = false
      node.isLeaf = true
    } else if (s === (y2 - y1 + 1) * (x2 - x1 + 1)) {
      node.val = true
      node.isLeaf = true
    } else {
      const mid = (x2 - x1) >> 1
      node.topLeft = dfs(start, [x1 + mid, y1 + mid])
      node.topRight = dfs([x1, y1 + mid + 1], [x1 + mid, y2])
      node.bottomLeft = dfs([x1 + mid + 1, y1], [x2, y1 + mid])
      node.bottomRight = dfs([x1 + mid + 1, y1 + mid + 1], end)
    }
    return node
  }

  return dfs([0, 0], [n - 1, n - 1])
}