🌕 427. 建立四叉树

难度: 🌕

问题描述

---

解法

/*
// 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) {
        // 思路：
        // 递归
        int len = grid.length;
        return mySol(grid, 0, len - 1, 0, len - 1);
    }

    private Node mySol(int[][] grid, int i1, int i2, int j1, int j2) {
        // 递归终止条件 - {i1, i2, j1, j2} 区域内全为 0 | 1 --> 叶子节点
        // System.out.println(i1 + "  " + i2 + "  " + j1 + "  " + j2);
        int tmp = grid[i1][j1];
        boolean only = true;
        for(int i = i1; i <= i2; i ++) {
            if(!only) {
                break;
            }
            for(int j = j1; j <= j2; j ++) {
                if(grid[i][j] != tmp) {
                    only = false;
                    break;
                }
            }
        }
        if(only) {
            // 说明 tmp 没有改变，全为 同一个值
            boolean b = (tmp == 1) ? true: false;
            return new Node(b, true); // 叶子节点
        }
        // 非叶子节点，还需要进一步拆分
        Node res = new Node(true, false);
        int midi = i1 + ((i2 - i1) >> 1);
        int midj = j1 + ((j2 - j1) >> 1);
        res.topLeft = mySol(grid, i1, midi, j1, midj);
        res.topRight = mySol(grid, i1, midi, midj + 1, j2);
        res.bottomLeft = mySol(grid, midi + 1, i2, j1, midj);
        res.bottomRight = mySol(grid, midi + 1, i2, midj + 1, j2);
        return res;
    }
}

---

输出