Algorithms first

建立四叉树 · 交互式算法学习

把 0/1 方阵构造成四叉树。

#427 · 分治

建立四叉树

Construct Quad Tree

测试用例grid = [[1,1],[1,1]]

矩阵3 个关键状态

进度 1 / 3速度

步骤 1建立二维前缀和。prefix ready

10,0

10,1

11,0

11,1

二维前缀和判断

时间 O(n²)空间 O(n²)

前缀和 O(1) 得到区域 1 的数量，快速判断全 0 或全 1。

1function construct(g) {2  const n = g.length,3    p = Array.from({4      length: n + 15    }, () => Array(n + 1).fill(0));6  for (let i = 0; i < n; i++)7    for (let j = 0; j < n; j++) p[i + 1][j + 1] = g[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j];8  const sum = (r, c, s) => p[r + s][c + s] - p[r][c + s] - p[r + s][c] + p[r][c];9 10  function build(r, c, s) {11    const x = sum(r, c, s);12    if (x === 0 || x === s * s) return new Node(x > 0, true);13    const h = s / 2;14    return new Node(true, false, build(r, c, h), build(r, c + h, h), build(r + h, c, h), build(r + h, c + h, h))15  }16  return build(0, 0, n);17}

多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/*2// Definition for a QuadTree node.3class Node {4    public boolean val;5    public boolean isLeaf;6    public Node topLeft;7    public Node topRight;8    public Node bottomLeft;9    public Node bottomRight;10 11 12    public Node() {13        this.val = false;14        this.isLeaf = false;15        this.topLeft = null;16        this.topRight = null;17        this.bottomLeft = null;18        this.bottomRight = null;19    }20 21    public Node(boolean val, boolean isLeaf) {22        this.val = val;23        this.isLeaf = isLeaf;24        this.topLeft = null;25        this.topRight = null;26        this.bottomLeft = null;27        this.bottomRight = null;28    }29 30    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node31bottomRight) { this.val = val; this.isLeaf = isLeaf; this.topLeft = topLeft; this.topRight =32topRight; this.bottomLeft = bottomLeft; this.bottomRight = bottomRight;33    }34};35*/36 37class Solution {38    public Node construct(int[][] grid) {39        return dfs(0, 0, grid.length - 1, grid[0].length - 1, grid);40    }41 42    private Node dfs(int a, int b, int c, int d, int[][] grid) {43        int zero = 0, one = 0;44        for (int i = a; i <= c; ++i) {45            for (int j = b; j <= d; ++j) {46                if (grid[i][j] == 0) {47                    zero = 1;48                } else {49                    one = 1;50                }51            }52        }53        boolean isLeaf = zero + one == 1;54        boolean val = isLeaf && one == 1;55        Node node = new Node(val, isLeaf);56        if (isLeaf) {57            return node;58        }59        node.topLeft = dfs(a, b, (a + c) / 2, (b + d) / 2, grid);60        node.topRight = dfs(a, (b + d) / 2 + 1, (a + c) / 2, d, grid);61        node.bottomLeft = dfs((a + c) / 2 + 1, b, c, (b + d) / 2, grid);62        node.bottomRight = dfs((a + c) / 2 + 1, (b + d) / 2 + 1, c, d, grid);63        return node;64    }65}

交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。

动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。

适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。

AlgoViz Lab

建立四叉树 · 解法对比

AlgoViz Lab2026-07-112026-07-12

把 0/1 方阵构造成四叉树。

测试用例: grid = [[1,1],[1,1]]
题目分类: 分治
解法对比: 2

方案 1

每块扫描是否同值

每次递归先扫描当前区域；若不全同再分四块。

时间: O(n² log n)
空间: O(log n)

方案 2

二维前缀和判断

前缀和 O(1) 得到区域 1 的数量，快速判断全 0 或全 1。

时间: O(n²)
空间: O(n²)