https://leetcode.cn/problems/construct-quad-tree/description/?envType=study-plan-v2&envId=top-interview-150

思路：這題乍一看很復雜但是只要讀懂題找到規律就會發現其實很簡單
四叉樹的構造規律：
1. 如果一個區域的值全相等，那么這個區域就是葉子節點，val = grid[x][y]==1, isLeaf = true。
2. 如果一個區域的值不全相等，那么這個區域就不是葉子節點，val = 隨意（true、false都行）, isLeaf = false。
3. 如果一個區域的值不全相等，那么這個新生成的節點不是葉節點所以有四個子節點，每個子節點對應一個子區域；反之葉節點不應該有子節點。

所以我們就可以對grid分治了，每次將它分成四個區域，如果某一區域不能再分了，我們就返回該區域對應節點（一定是leaf），遞歸結束后我們再按規律合并這四個區域。

class Solution {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;}}public Node construct(int[][] grid) {Node root = divide(grid, 0, 0, grid.length - 1, grid[0].length - 1);return root;}public Node divide(int[][] grid, int x1, int y1, int x2, int y2) {if( x1 == x2 && y1 == y2) {return new Node(grid[x1][y1] == 1, true);}// 把這個區域分成四部分int topLeft_x1 = x1, topLeft_y1 = y1, topLeft_x2 = (x1 + x2) / 2, topLeft_y2 = (y1 + y2) / 2;int topRight_x1 = x1, topRight_y1 = topLeft_y2 + 1, topRight_x2 = topLeft_x2, topRight_y2 = y2;int bottomLeft_x1 = topLeft_x2 + 1, bottomLeft_y1 = y1, bottomLeft_x2 = x2, bottomLeft_y2 = topLeft_y2;int bottomRight_x1 = bottomLeft_x1, bottomRight_y1 = topLeft_y2 + 1, bottomRight_x2 = x2, bottomRight_y2 = y2;Node topLeftNode = divide(grid, topLeft_x1, topLeft_y1, topLeft_x2, topLeft_y2);Node topRightNode = divide(grid, topRight_x1, topRight_y1, topRight_x2, topRight_y2);Node bottomLeftNode = divide(grid, bottomLeft_x1, bottomLeft_y1, bottomLeft_x2, bottomLeft_y2);Node bottomRightNode = divide(grid, bottomRight_x1, bottomRight_y1, bottomRight_x2, bottomRight_y2);return merge(topLeftNode, topRightNode, bottomLeftNode, bottomRightNode);}public Node merge(Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {// 如果所有子節點全是葉子節點并且它們的值全相等就說明新被構造出的節點也是葉子節點// 注意新構造出的葉子節點沒有子節點if(topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf&& topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {return new Node(topLeft.val, true, null, null, null, null);} else { // 否則新構造出的節點不是葉子節點，該節點的值隨意return new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);}}public static void main(String[] args) {Solution solution = new Solution();int[][] 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}};solution.construct(grid);}
}