通过万岁！！！
- 题目：就是给你一个n*n的数组，然后我们构建一个四叉树。就是把数组进行4等分，然后四个部分是四叉树的四个分支。只不过在这个过程中有一些规则。
- 如果这个数组（确切的说是子数组），里面的元素全部都是一样的，那么就他就是叶子节点，所以他的isLeaf=true，然后因为数组中的值是一样的，所以他的val等于这个数组中的任意一个元素即可。
- 如果数组中的元素不一样，那么就递归的找就行了，直到不能划分，也就是变成了1*1的单元格，我们停止即可。因为下面的值是不一样的，所以本层的值随便写。
- 思路：
- 其实就是分治算法，我们将其一直进行划分，直到划到了1*1，我们就进行处理，这时候一定是一个叶子节点，并且值是里面的值。处理好了，我们将这个node对象返回出去。
- 然后就是m*m的时候，这时候我们通过递归拿到了所有的子树，然后其实都看一下子树中的val是不是都是一样的，就可以了。如果一样，则合并成一个叶子节点即可。
- 但是存在一个问题，下图左边的时候，我们到底认为这个节点的val是多少。如果认为是1，则再次递归到上面时（下图右侧），黄色，橙色，绿色，蓝色的val都是1，那么他们应该是合并成一个，全都是1。但是其实不能进行合并。
- 所以，我们要先判断下面的四个子节点是不是全是叶子节点，如果全是叶子，那么就保证了里面的所有的val都是一样的。并且这四个的val全是一样的，那么我们就合并成一个叶子节点。否则，下面的叶子节点不能进行合并，所以本节点不是叶子节点。
- 技巧：就是用到了分治，只不过这里在合并的时候，需要两步的判断。
java代码——代码行相对长一点
class Solution {
public Node construct(int[][] grid) {
// 这个题其实就是典型的分治算法，先写分治的框架
int n = grid.length - 1;
return getAns(grid, 0, n, 0, n);
}
private Node getAns(int[][] grid, int startHang, int endHang, int startLie, int endLie) {
if (startHang == endHang) {// 只剩下一个单元格了
return new Node(grid[startHang][endLie] == 1, true);
}
int len = (endHang - startHang) / 2;
// 下面从start-mid，end-mid
Node topLeft = getAns(grid, startHang, startHang + len, startLie, startLie + len);
Node bottomLeft = getAns(grid, endHang - len, endHang, startLie, startLie + len);
Node topRight = getAns(grid, startHang, startHang + len, endLie - len, endLie);
Node bottomRight = getAns(grid, endHang - len, endHang, endLie - len, endLie);
Node ans;
if (topLeft.isLeaf && bottomLeft.isLeaf && topRight.isLeaf && bottomRight.isLeaf) {// 下面全是叶子，
if (topLeft.val == bottomLeft.val
&& topLeft.val == topRight.val
&& topLeft.val == bottomRight.val) {// val还一样，下面的叶子不要了，当前是叶子，也就是进行叶子节点的合并
ans = new Node(topLeft.val, true);
} else {// 值不一样，表示当前不是叶子
ans = new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);
}
} else {// 有叶子，也有非叶子，则当前不是叶子
ans = new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);
}
return ans;
}
}
java代码——代码行相对短一点
class Solution {
public Node construct(int[][] grid) {
// 这个题其实就是典型的分治算法，先写分治的框架
int n = grid.length - 1;
return getAns(grid, 0, n, 0, n);
}
private Node getAns(int[][] grid, int startHang, int endHang, int startLie, int endLie) {
if (startHang == endHang) {// 只剩下一个单元格了
return new Node(grid[startHang][endLie] == 1, true);
}
int len = (endHang - startHang) / 2;
// 下面从start-mid，end-mid
Node topLeft = getAns(grid, startHang, startHang + len, startLie, startLie + len);
Node bottomLeft = getAns(grid, endHang - len, endHang, startLie, startLie + len);
Node topRight = getAns(grid, startHang, startHang + len, endLie - len, endLie);
Node bottomRight = getAns(grid, endHang - len, endHang, endLie - len, endLie);
if (topLeft.isLeaf && bottomLeft.isLeaf && topRight.isLeaf && bottomRight.isLeaf) {// 下面全是叶子，
if (topLeft.val == bottomLeft.val
&& topLeft.val == topRight.val
&& topLeft.val == bottomRight.val) {// val还一样，下面的叶子不要了，当前是叶子，也就是进行叶子节点的合并
return new Node(topLeft.val, true);
}
}
return new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);
}
}
- 总结：题目有点绕，不太好理解，并且这里的判断关系，也相对复杂，不过还是挺有意思的。
