2023-02-27.md

题目

427. Construct Quad Tree

Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

思路

代码

// runtime 86.36% memory 45.45%
var construct = function (grid) {
  function dfs(x, y, length) {
    if (length == 1) return new Node(grid[y][x] == 1, true)
    const topLeft = dfs(x, y, length / 2)
    const topRight = dfs(x + length / 2, y, length / 2)
    const bottomLeft = dfs(x, y + length / 2, length / 2)
    const bottomRight = dfs(x + length / 2, y + length / 2, length / 2)
    if (
      topLeft.isLeaf &&
      topRight.isLeaf &&
      bottomLeft.isLeaf &&
      bottomRight.isLeaf &&
      topLeft.val == topRight.val &&
      topRight.val == bottomLeft.val &&
      bottomLeft.val == bottomRight.val
    ) {
      return new Node(topLeft.val, true)
    }
    return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight)
  }
  return dfs(0, 0, grid.length)
}