leetcode 427. Construct Quad Tree | 427. 建立四叉树（分治法）

川长思鸟来 2022-09-03 15:20 3阅读 0赞

## 题目 ##

[https://leetcode.com/problems/construct-quad-tree/][https_leetcode.com_problems_construct-quad-tree]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

## 题解 ##

/* // 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) { 
            // x,y,size确定一个正方形
            Node root = partition(grid, 0, 0, grid.length);
            return root;
        }
    
        // 通过4个val判断是否有相异元素
        public Node partition(int[][] grid, int x, int y, int size) { 
            Node node = new Node();
            if (size == 1) { 
                node.isLeaf = true;
                node.val = (grid[x][y] == 1);
                return node;
            }
    
            Node TL = partition(grid, x, y, size / 2);
            Node TR = partition(grid, x, y + size / 2, size / 2);
            Node BL = partition(grid, x + size / 2, y, size / 2);
            Node BR = partition(grid, x + size / 2, y + size / 2, size / 2);
    
            if (TL.isLeaf && TR.isLeaf && BL.isLeaf && BR.isLeaf && TL.val == TR.val && TR.val == BL.val && BL.val == BR.val) {  // 四叶子合并
                node.isLeaf = true;
                node.val = TL.val;
            } else {  // 四叶子无法合并
                node.isLeaf = false;
                node.topLeft = TL;
                node.topRight = TR;
                node.bottomLeft = BL;
                node.bottomRight = BR;
            }
            return node;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_construct-quad-tree]: https://leetcode.com/problems/construct-quad-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/566b9ba748d74b9386343221b49ee343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/0cbf34932b3e454493498e1ea0435657.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/dfacab9bfd4e4eb990e4384b69e97340.png