LC.P427[建立四叉树]

方法一：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    int[][] grid;

    public Node construct(int[][] grid) {
        this.grid = grid;
        int n = grid.length;
        return dfs(0, 0, n - 1, n - 1);
    }

    private Node dfs(int a, int b, int c, int d) {
        boolean flag = true;
        int t = grid[a][b];
        for (int i = a; i <= c && flag; ++i) {
            for (int j = b; j <= d && flag; ++j) {
                if (grid[i][j] != t) flag = false;
            }
        }
        if (flag) return new Node(t == 1, true);
        int dx = c - a + 1, dy = d - b + 1;
        return new Node(
                t == 1,
                false,
                dfs(a, b, a + dx / 2 - 1, b + dy / 2 - 1), // 左上
                dfs(a, b + dy / 2, a + dx / 2 - 1, d),     // 右上
                dfs(a + dx / 2, b, c, b + dy / 2 - 1),     // 左下
                dfs(a + dx / 2, b + dy / 2, c, d)          // 右下
        );
    }
}
  • 时间复杂度：$O(n^2 + n^2logn)$
  • 空间复杂度：$O(1)$

方法二：DFS优化

判断节点是否为叶子节点只需要判断其四个子节点是否都为叶子节点并且它们的val都相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    int[][] grid;

    public Node construct(int[][] grid) {
        this.grid = grid;
        return dfs(0, 0, grid.length);
    }

    private Node dfs(int top, int left, int size) {
        if (size == 1) return new Node(grid[top][left] == 1, true);
        int subSize = size / 2;
        Node topLeft = dfs(top, left, subSize);
        Node topRight = dfs(top, left + subSize, subSize);
        Node bottomLeft = dfs(top + subSize, left, subSize);
        Node bottomRight = dfs(top + subSize, left + subSize, subSize);
        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
                topLeft.val == topRight.val && topLeft.val == bottomLeft.val && topLeft.val == bottomRight.val) {
            return new Node(topLeft.val, true);
        } else {
            return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
}

方法三：前缀和优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    int[][] grid;
    int[][] sum;

    public Node construct(int[][] grid) {
        this.grid = grid;
        int n = grid.length;
        sum = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }
        return dfs(0, 0, n - 1, n - 1);
    }

    private Node dfs(int a, int b, int c, int d) {
        int cur = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b];
        int dx = c - a + 1, dy = d - b + 1, total = dx * dy;
        if (cur == 0 || cur == total) return new Node(grid[a][b] == 1, true);
        return new Node(
                grid[a][b] == 1,
                false,
                dfs(a, b, a + dx / 2 - 1, b + dy / 2 - 1),
                dfs(a, b + dy / 2, a + dx / 2 - 1, d),
                dfs(a + dx / 2, b, c, b + dy / 2 - 1),
                dfs(a + dx / 2, b + dy / 2, c, d)
        );
    }
}
  • 时间复杂度：$O(n^2 + logn)$
  • 空间复杂度：$O(n^2)$