[数据结构与算法]Construct Quad Tree

Given a?n * n?matrix?grid?of?0's?and?1's?only. We want to represent the?grid?with a Quad-Tree.

Return?the root of the Quad-Tree?representing the?grid.

Notice that you can assign the value of a node to?True?or?False?when?isLeaf?is?False, and both are?accepted?in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
• isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

Example 2:

Input: 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]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

思路：DFS，如果四个node全部是isLeaf，那么直接返回node，否则继续递归；

/*
// 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 helper(grid, 0, 0, grid.length);
    }
    
    private Node helper(int[][] grid, int x, int y, int len) {
        if(len == 1) {
            return new Node(grid[x][y] == 1, true, null, null, null, null);
        } else {
            Node node = new Node();
            Node topLeft = helper(grid, x, y, len / 2);
            Node topRight = helper(grid, x, y + len / 2, len / 2);
            Node bottomLeft = helper(grid, x + len / 2, y, len / 2);
            Node bottomRight = helper(grid, x + len / 2, y + len / 2, len / 2);
            if(topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
              && topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
                // 如果四个node，分别都是叶子节点，而且value全部相同，那么这个大的node就是个叶子节点；不用再递归了；
                node.isLeaf = true;
                node.val = topLeft.val;
            } else {
                // 否则，那这个node的四个node还需要用递归结果；
                node.topLeft = topLeft;
                node.topRight = topRight;
                node.bottomLeft = bottomLeft;
                node.bottomRight = bottomRight;
            }
            return node;
        }
    }
}