Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 1302. Deepest Leaves Sum in F#

Shohei Yoshida's photo
Shohei Yoshida
·May 15, 2022·

1 min read

URL

leetcode.com/problems/deepest-leaves-sum

Code

github.com/syohex/dotnet-study/blob/master/..

open System

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

let deepestLeaveSum (root: Tree) : int =
    let rec deepestLeaveSum' node depth acc =
        match node with
        | Leaf -> depth - 1, acc
        | Node (v, left, right) ->
            let leftDepth, accLeft = deepestLeaveSum' left (depth + 1) acc
            let rightDepth, accRight = deepestLeaveSum' right (depth + 1) accLeft

            let acc' =
                match Map.tryFind depth accRight with
                | None -> Map.add depth v accRight
                | Some (n) -> Map.add depth (v + n) accRight

            Math.Max(leftDepth, rightDepth), acc'

    deepestLeaveSum' root 0 Map.empty ||> Map.find
 
Share this