ChunNote
0%

leetCode-427:Construct Quad Tree

发表于 分类于

问题描述

给定一个 n * n 的二维数组（n = 1,2,4,6,8,16,32,64)，数组元素为 0 或 1。要求将数组构造成一个四叉树。构造树的规则如下，如果一个正方形内元素都是 0 或 1，那么由该正方形构成一个叶子节点，节点元素值为 true (正方形元素都是 1)或 false (正方形元素都是0)，如果一个正方形内的元素不同，则该正方形代表一个非叶子节点，且则将正方形均分成四个小正方形，作为该非叶子节点的子节点。题目链接：点我

样例输入输出

输入：grid = [[0,1],[1,0]]

输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]

解释：其输出的树如下

输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]

输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

解释：其输出的树如下

问题解法

此题关键在于读懂题目，读懂题目后，就是常规的递归构造树的方式。代码如下

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 {
    public Node construct(int[][] grid) {
        return build(grid, 0, grid.length - 1, 0, grid[0].length - 1);
    }

    private Node build(int[][] grid, int iStart, int iEnd, int jStart, int jEnd) {
        if (isSame(grid, iStart, iEnd, jStart, jEnd)) {
            return new Node(grid[iStart][jStart] == 1, true);
        }

        Node topLeft = build(grid, iStart, (iStart + iEnd) / 2, jStart, (jStart + jEnd) / 2);
        Node topRight = build(grid, iStart, (iStart + iEnd) / 2, (jStart + jEnd) / 2 + 1, jEnd);
        Node bottomLeft = build(grid, (iStart + iEnd) / 2 + 1, iEnd, jStart, (jStart + jEnd) / 2);
        Node bottomRight = build(grid, (iStart + iEnd) / 2 + 1, iEnd, (jStart + jEnd) / 2 + 1, jEnd);
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }

    private boolean isSame(int[][] grid, int iStart, int iEnd, int jStart, int jEnd) {
        int first = grid[iStart][jStart];
        for (int i = iStart; i <= iEnd; i++) {
            for (int j = jStart; j <= jEnd; j++) {
                if (grid[i][j] != first) {
                    return false;
                }
            }
        }

        return true;
    }
}