LeetCode 2096. Step-By-Step Directions From a Binary Tree Node to Another in F#

URL

Step-By-Step Directions From a Binary Tree Node to Another - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202407/step-by-step-directions-from-a-binary-tree-node-to-another/main.fsx

open System

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

let getDirections (root: Tree) (startValue: int) (destValue: int) : string =
    let rec findPath node value acc =
        match node with
        | Leaf -> []
        | Node(v, left, right) ->
            if v = value then
                List.rev acc
            else
                match findPath left value ('L' :: acc) with
                | [] -> findPath right value ('R' :: acc)
                | ret -> ret

    let rec getDirections' (startPath: char list) (destPath: char list) =
        match startPath, destPath with
        | [], [] -> ""
        | s, [] -> List.init (List.length s) (fun _ -> 'U') |> String.Concat
        | [], d -> d |> String.Concat
        | h1 :: t1, h2 :: t2 ->
            if h1 = h2 then
                getDirections' t1 t2
            else
                List.init (List.length startPath) (fun _ -> 'U') @ destPath |> String.Concat

    let startPath = findPath root startValue []
    let destPath = findPath root destValue []

    getDirections' startPath destPath