URL

Maximum Level Sum of a Binary Tree - LeetCode

Code

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

open System

type Tree =
    | Leaf
    | Node of int * Tree * Tree

let maxLevelSum (root: Tree) : int =
    let rec maxLevelSum' node level acc =
        match node with
        | Leaf -> acc
        | Node(v, left, right) ->
            let acc' =
                match Map.tryFind level acc with
                | Some(n) -> Map.add level (n + v) acc
                | None -> Map.add level v acc

            let acc'' = maxLevelSum' left (level + 1) acc'
            maxLevelSum' right (level + 1) acc''

    maxLevelSum' root 1 Map.empty
    |> Map.fold
        (fun (max, ret) k v -> if v > max || (v = max && k < ret) then v, k else max, ret)
        (Int32.MinValue, Int32.MaxValue)
    |> snd