[LeetCode] 558. Logical OR of Two Binary Grids Represented as Quad-Trees

😎풀이

1. 비교하는 두 대상 중 한쪽이 Leaf 노드라면
   1-1. Leaf 노드의 값이 true인 경우 OR 연산은 반드시 true 이므로 즉시 반환
   1-2. Leaf 노드의 값이 false인 경우 OR 연산은 이후 노드 반환
2. 두 대상 모두 부모 노드라면
   2-1. 4방향 깊이 우선 탐색
   2-2. 모든 노드가 Leaf이며, 값이 동일한 경우 해당 값을 갖는 Leaf 노드 반환
   2-3. 아닌 경우, 중간 관리자 노드로 설정하여 반환

function intersect(quadTree1: _Node | null, quadTree2: _Node | null): _Node | null {
    if(quadTree1.isLeaf && quadTree2.isLeaf) {
        const val = quadTree1.val || quadTree2.val
        return new _Node(val, true)
    }
    if(quadTree1.isLeaf) {
        if(quadTree1.val === true) return new _Node(true, true)
        return quadTree2
    }
    if(quadTree2.isLeaf) {
        if(quadTree2.val === true) return new _Node(true, true)
        return quadTree1
    }
    const tl = intersect(quadTree1.topLeft, quadTree2.topLeft)
    const tr = intersect(quadTree1.topRight, quadTree2.topRight)
    const bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
    const br = intersect(quadTree1.bottomRight, quadTree2.bottomRight)
    const allIsLeaf = tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf
    const allValSame = tl.val === tr.val && tr.val === bl.val && bl.val === br.val
    if(allIsLeaf && allValSame) {
        return new _Node(tl.val, true)
    }
    return new _Node(false, false, tl, tr, bl, br)
};