URL

Construct Quad Tree - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0427/main.fsx

type QuadTree =
    | Leaf
    | Node of int * bool * QuadTree * QuadTree * QuadTree * QuadTree

let construct (grid: int[,]) : QuadTree =
    let check n x y =
        let mutable v = grid.[x, y]

        for i in 0 .. (n - 1) do
            for j in 0 .. (n - 1) do
                if v <> -1 && v <> grid.[x + i, y + j] then
                    v <- -1

        v

    let rec construct' n x y =
        let v = check n x y

        if v <> -1 then
            Node(v, true, Leaf, Leaf, Leaf, Leaf)
        else
            let n' = n / 2
            let topLeft = construct' n' x y
            let topRight = construct' n' x (y + n')
            let bottomLeft = construct' n' (x + n') y
            let bottomRight = construct' n' (x + n') (y + n')

            Node(1, false, topLeft, topRight, bottomLeft, bottomRight)

    construct' (Array2D.length1 grid) 0 0