LeetCode.558. 四叉树交集___分治

题目链接：

558. 四叉树交集

Solution:

• 主要在于理解好题意，其实就是一个递归问题，具体见代码注释。

Code:

/* // 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() {} public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) { val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight; } }; */


/* 明确递归函数意义 */
class Solution {
    
    public Node intersect(Node quadTree1, Node quadTree2) {
    
        if(quadTree1.isLeaf){
    
            if(quadTree1.val){
    
                return new Node(true,true);
            }
            return new Node(quadTree2.val,quadTree2.isLeaf,quadTree2.topLeft,quadTree2.topRight,quadTree2.bottomLeft,quadTree2.bottomRight);
        }

        if(quadTree2.isLeaf){
    
            if(quadTree2.val){
    
                return new Node(true,true);
            }
            return new Node(quadTree1.val,quadTree1.isLeaf,quadTree1.topLeft,quadTree1.topRight,quadTree1.bottomLeft,quadTree1.bottomRight);
        }

        Node node1 = intersect(quadTree1.topLeft,quadTree2.topLeft);
        Node node2 = intersect(quadTree1.topRight,quadTree2.topRight);
        Node node3 = intersect(quadTree1.bottomLeft,quadTree2.bottomLeft);
        Node node4 = intersect(quadTree1.bottomRight,quadTree2.bottomRight);
        
        // 四个子节点的值要一样，且要保证他们均为叶子节点
        // 因为原先是构建的时候，而构建其实就是造的节点都为新节点，即为子节点
        if(node1.isLeaf && node2.isLeaf && node3.isLeaf && node4.isLeaf && node1.val == node2.val 
                && node1.val == node3.val && node1.val == node4.val){
    
                    // 成功则代表其会融合为一个新的叶子节点
                return new Node(node1.val,true);
        }

        return new Node(false,false,node1,node2,node3,node4);
    }
}