# 0427. Construct Quad Tree
###### tags: `Leetcode` `Recursion` `Medium`
Link: https://leetcode.com/problems/construct-quad-tree/description/
## Code

class Solution {
    public Node construct(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        return dfs(grid, 0, m-1, 0, n-1);
    }
    private Node dfs(int[][] grid, int startx, int endx, int starty, int endy){
        if(startx==endx && starty==endy) return new Node(grid[startx][starty]==1, true);
        Node root = new Node();
        int midx = (startx+endx)/2, midy = (starty+endy)/2;
        Node topLeft = dfs(grid, startx, midx, starty, midy);
        Node topRight = dfs(grid, startx, midx, midy+1, endy);
        Node bottomLeft = dfs(grid, midx+1, endx, starty, midy);
        Node bottomRight = dfs(grid, midx+1, endx, midy+1, endy);
        if(topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf && topLeft.val==topRight.val && topRight.val==bottomLeft.val && bottomLeft.val==bottomRight.val){
            root.val = topLeft.val;
            root.isLeaf = true;
        }
        else{
            root.topLeft = topLeft;
            root.topRight = topRight;
            root.bottomLeft = bottomLeft;
            root.bottomRight = bottomRight;
        }
        return root;
    }

    
}