URL

Construct String from Binary Tree - LeetCode

Code

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

open System

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

let tree2Str (root: TreeNode) : string =
    let rec tree2Str' (node: TreeNode) (acc: string list) =
        match node with
        | Leaf -> acc
        | Node(v, left, right) ->
            let acc' = (string v) :: acc

            match left, right with
            | Leaf, Leaf -> acc'
            | Node(_), Leaf ->
                let acc'' = tree2Str' left ("(" :: acc')
                ")" :: acc''
            | Leaf, Node(_) ->
                let acc' = tree2Str' right ("(" :: ")" :: "(" :: acc')
                ")" :: acc'
            | _ ->
                let acc'' = tree2Str' left ("(" :: acc')
                let acc''' = tree2Str' right ("(" :: ")" :: acc'')
                ")" :: acc'''

    tree2Str' root [] |> List.rev |> String.Concat