URL

Maximum Difference Between Node and Ancestor - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202401/maximum_difference_between_node_and_ancestor/main.fsx

open System

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

let maxAncestorDiff (root: Tree) : int =
    let rec maxAncestorDiff' node min max =
        match node with
        | Leaf -> -1
        | Node(v, left, right) ->
            let ret = Math.Max(Math.Abs(v - min), Math.Abs(v - max))
            let min', max' = Math.Min(v, min), Math.Max(v, max)
            let leftRet = maxAncestorDiff' left min' max'
            let rightRet = maxAncestorDiff' right min' max'
            Math.Max(ret, Math.Max(leftRet, rightRet))

    match root with
    | Leaf -> failwith "never reach here"
    | Node(v, _, _) -> maxAncestorDiff' root v v