[LeetCode] 427. Construct Quad Tree

😎풀이

1. 깊이 우선탐색을 통해 절반씩 검증하며 leaf 노드 탐색
2. 부모 노드의 4방면을 확인하며, 스택 종료
3. 자식 요소가 모두 정의된 root 노드 반환

function construct(grid: number[][]): _Node | null {
    function dfs(r: number, c: number, size: number) {
        let isSame = true
        outer: for(let i = r; i < r + size; i++) {
            for(let j = c; j < c + size; j++) {
                if(grid[i][j] === grid[r][c]) continue
                isSame = false
                break outer
            }
        }
        if(isSame) return new Node(grid[r][c] === 1, true)
        const half = size / 2
        return new Node(
            false,
            false,
            dfs(r, c, half),
            dfs(r, c + half, half),
            dfs(r + half, c, half),
            dfs(r + half, c + half, half)
        )
    }
    return dfs(0, 0, grid.length)
};