leetcode 558. Logical OR of Two Binary Grids Represented as Quad-Trees | 558. 四叉树交集（分治法）

红太狼 2022-08-28 10:51 6阅读 0赞

## 题目 ##

[https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/][https_leetcode.com_problems_logical-or-of-two-binary-grids-represented-as-quad-trees]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

自己写的没通过，这题不方便构造测试用例，没有找到问题在哪儿。后来看了答案：[https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/discuss/157532/Java-concise-code-beat-100][https_leetcode.com_problems_logical-or-of-two-binary-grids-represented-as-quad-trees_discuss_157532_Java-concise-code-beat-100]

class Solution { 
        public Node intersect(Node n1, Node n2) { 
            if (n1.isLeaf) return n1.val ? n1 : n2;
            if (n2.isLeaf) return n2.val ? n2 : n1;
    
            n1.topLeft = intersect(n1.topLeft, n2.topLeft);
            n1.topRight = intersect(n1.topRight, n2.topRight);
            n1.bottomLeft = intersect(n1.bottomLeft, n2.bottomLeft);
            n1.bottomRight = intersect(n1.bottomRight, n2.bottomRight);
    
            // try merge leaf
            if (n1.topLeft.isLeaf && n1.topRight.isLeaf && n1.bottomLeft.isLeaf && n1.bottomRight.isLeaf &&
                    n1.topLeft.val == n1.topRight.val && n1.topRight.val == n1.bottomLeft.val && n1.bottomLeft.val == n1.bottomRight.val) { 
                n1.isLeaf = true;
                n1.val = n1.topRight.val;
                n1.topLeft = null;
                n1.topRight = null;
                n1.bottomLeft = null;
                n1.bottomRight = null;
            }
            return n1;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_logical-or-of-two-binary-grids-represented-as-quad-trees]: https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4dc741a45b664717989f118d913ff489.png
[https_leetcode.com_problems_logical-or-of-two-binary-grids-represented-as-quad-trees_discuss_157532_Java-concise-code-beat-100]: https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/discuss/157532/Java-concise-code-beat-100
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d7775d7cf02b43d78abd8f9d162829c4.png