URL

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/description/

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202401/pseudo-palindromic-paths-in-a-binary-tree/main.fsx

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

let isPseudoPalindrom m len =
    let odd = Map.values m |> Seq.filter (fun n -> n % 2 <> 0) |> Seq.length
    if len % 2 = 0 then odd = 0 else odd = 1

let pseudoPalindromicPaths (root: Tree) : int =
    let rec pseudoPalindromicPaths' node m len =
        match node with
        | Leaf -> 0
        | Node(v, Leaf, Leaf) ->
            let m' =
                match Map.tryFind v m with
                | Some(a) -> Map.add v (a + 1) m
                | None -> Map.add v 1 m

            if isPseudoPalindrom m' len then 1 else 0
        | Node(v, left, right) ->
            let m' =
                match Map.tryFind v m with
                | Some(a) -> Map.add v (a + 1) m
                | None -> Map.add v 1 m

            let a = pseudoPalindromicPaths' left m' (len + 1)
            let b = pseudoPalindromicPaths' right m' (len + 1)
            a + b

    pseudoPalindromicPaths' root Map.empty 1