LeetCode 558. 四叉树交集

558. 四叉树交集

【分治+递归】这道题太长了，但是我们可以简单梳理一下：

1.如果两个节点任何一个为叶子：

        如果叶子是1，那么直接返回为1的叶子就行

        如果叶子是0，那么直接返回另一个节点

2.递归处理四个孩子，分别得到四个递归后的结果

        如果四个都是叶子，

                如果都是1，返回一个合并后的大1节点

                如果都是0，返回一个合并后的大0节点

        否则，返回根据四个递归节点创建一个大节点

/*
// 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 {

    // 4.12 16

    public Node dfs(Node n1, Node n2) {
        Node node = new Node();
        if (n1.isLeaf) {
            if (n1.val == true) return new Node(true, true, null, null, null, null);
            else return n2;
        } 
        if (n2.isLeaf) {
            if (n2.val == true) return new Node(true, true, null, null, null, null);
            else return n1;
        }
        Node tl = dfs(n1.topLeft, n2.topLeft);
        Node tr = dfs(n1.topRight, n2.topRight);
        Node bl = dfs(n1.bottomLeft, n2.bottomLeft);
        Node br = dfs(n1.bottomRight, n2.bottomRight);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf) {
            if (tl.val && tr.val && bl.val && br.val) {
                return new Node(true, true, null, null, null, null);
            }
            if (tl.val == false && tr.val == false && bl.val == false && br.val == false) {
                return new Node(false, true, null, null, null, null);
            }
        }
        return new Node(false, false, tl, tr, bl, br);
    }

    public Node intersect(Node quadTree1, Node quadTree2) {
        return dfs(quadTree1, quadTree2);
    }
}