跳到主要内容

427.建立四叉树

链接：427.建立四叉树
难度：Medium
标签：树、数组、分治、矩阵
简介：你需要返回能表示矩阵的 四叉树 的根结点。

题解 1 - cpp​

  • 编辑时间：2022-04-29
  • 执行用时：24ms
  • 内存消耗：23.7MB
  • 编程语言：cpp
  • 解法介绍：dfs。
class Solution {
   public:
    Node *construct(vector<vector<int>> &grid) {
        int n = grid.size(), check;
        return dfs(grid, 0, n - 1, 0, n - 1, &check);
    }
    Node *dfs(vector<vector<int>> &grid, int srow, int erow, int scol, int ecol,
              int *check) {
        if (srow == erow && scol == ecol) {
            *check = 1;
            return getNode(grid[srow][scol], true);
        }
        int mrow = (erow + srow) >> 1, mcol = (ecol + scol) >> 1;
        int checkTL, checkTR, checkBL, checkBR;
        Node *tl = dfs(grid, srow, mrow, scol, mcol, &checkTL),
             *tr = dfs(grid, srow, mrow, mcol + 1, ecol, &checkTR),
             *bl = dfs(grid, mrow + 1, erow, scol, mcol, &checkBL),
             *br = dfs(grid, mrow + 1, erow, mcol + 1, ecol, &checkBR);
        if (tl->val == tr->val && tl->val == bl->val && tl->val == br->val &&
            checkTL & checkTR & checkBL & checkBR) {
            *check = 1;
            int val = tl->val;
            free(tl);
            free(tr);
            free(bl);
            free(br);
            return getNode(val, true);
        }
        Node *node = getNode(tl->val ^ tr->val ^ bl->val ^ br->val, false);
        *check = 0;
        node->topLeft = tl;
        node->topRight = tr;
        node->bottomLeft = bl;
        node->bottomRight = br;
        return node;
    }
    Node *getNode(bool val, bool isLeaf) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->isLeaf = isLeaf;
        node->val = val;
        node->topLeft = node->topRight = node->bottomLeft = node->bottomRight =
            nullptr;
        return node;
    }
};

题解 2 - go​

  • 编辑时间：2022-04-29
  • 执行用时：12ms
  • 内存消耗：6.5MB
  • 编程语言：go
  • 解法介绍：递归看是否成树。
func construct(grid [][]int) *Node {
    n := len(grid)
    return dfs(grid, 0, n-1, 0, n-1)
}
func dfs(grid [][]int, srow, erow, scol, ecol int) *Node {
    mrow, mcol := (srow+erow)>>1, (scol+ecol)>>1
    for i := srow; i <= erow; i++ {
        for j := scol; j <= ecol; j++ {
            if grid[i][j] != grid[srow][scol] {
                return &Node{
                    Val:         false,
                    IsLeaf:      false,
                    TopLeft:     dfs(grid, srow, mrow, scol, mcol),
                    TopRight:    dfs(grid, srow, mrow, mcol+1, ecol),
                    BottomLeft:  dfs(grid, mrow+1, erow, scol, mcol),
                    BottomRight: dfs(grid, mrow+1, erow, mcol+1, ecol),
                }
            }
        }
    }
    return &Node{Val: grid[srow][scol] == 1, IsLeaf: true}
}