day82（2.10）——leetcode面试经典150

427. 建立四叉树

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 n = grid.length; return build(grid, 0, n-1, 0, n-1); } Node build(int[][] grid, int l1, int r1, int l2, int r2) { int flag = 0; int d = grid[l1][l2]; for(int i=l1;i<=r1;i++) { for(int j=l2;j<=r2;j++) { if(grid[i][j]!=d) { flag=1; break; } } if(flag==1) { break; } } //如果该区域都相等，直接返回Node if(flag==0) { return new Node(d == 1, true); } int mid1 = (l1+r1)/2; int mid2 = (l2+r2)/2; Node tL = build(grid, l1, mid1, l2, mid2); Node tR = build(grid, l1, mid1, mid2+1, r2); Node bL = build(grid, mid1+1, r1, l2, mid2); Node bR = build(grid, mid1+1, r1, mid2+1, r2); return new Node(false, false, tL, tR, bL, bR); } }