建立四叉树

2024-03-21 15:44

文章标签 建立四叉树

本文主要是介绍建立四叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

建立四叉树

题目描述

注意点

n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6

解答思路

本题相当于要将一个大正方形不断划分为四个小正方形（如果大正方形中元素不完全相同），所以考虑使用分治，思路为：根据top、left和边长确定一个正方形，遍历正方形中每个点的值，如果值都相同说明其为叶子节点，没有子树，将isLeaf和val赋值即可；如果有值不相同说明其含有子树，将isLeaf和val赋值后，还要将当前正方形划分为4个小正方形并重复上述操作

代码

class Solution {public Node construct(int[][] grid) {return divide(grid, 0, 0, grid.length);}public Node divide(int[][] grid, int top, int left, int len) {boolean isLeaf = true;int val = grid[top][left];for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {if (grid[top + i][left + j] != val) {isLeaf = false;break;}}if (!isLeaf) {break;}}Node root = new Node();root.isLeaf = isLeaf;root.val = (val == 1);// 方格内元素不同，继续分治if (!isLeaf) {len = len / 2;root.topLeft = divide(grid, top, left, len);root.topRight = divide(grid, top, left + len, len);root.bottomLeft = divide(grid, top + len, left, len);root.bottomRight = divide(grid, top + len, left + len, len);}return root;}
}