如何获得最小深度的叶子？

Question

例如，我有这样的结构树

let tr = Node(1,[Node(2,[Leaf(5)]);Node(3,[Leaf(6);Leaf(7)]);Leaf(4)]) 

我怎样才能用最小深度叶？

Answer 1

let minDepthLeaf tree = 
    let rec aux (depth: int) = function 
    | Leaf(_) as l -> (l, depth) 
    | Node(_, children) -> children |> List.map (aux (depth+1)) |> List.minBy snd 

    aux 0 tree |> fst 

Answer 2

解决此问题的一种方法是实施Breadth-First Search算法。该算法在“levels”中遍历一棵树，以便返回根，然后返回根的所有孩子，然后返回这些孩子的所有孩子，等等。你可以把它写成一个返回序列的F＃函数：

/// Breadth-first search over a tree 
/// Takes list of initial nodes as argument 
let rec breadthFirstSearch nodes = seq { 
    // Return all nodes at the current level 
    yield! nodes 
    // Collect all children of current level 
    let children = nodes |> List.collect (function 
    | Leaf _ -> [] | Node(_, c) -> c) 
    // Walk over all the children (next level) 
    if children <> [] then 
    yield! breadthFirstSearch children } 

这对于各种树处理任务是非常有用的算法，所以它是有用的。现在，为了获得最低Leaf，你可以随便挑序列中的第一Leaf节点：

breadthFirstSearch [tr] 
|> Seq.filter (function Leaf _ -> true | _ -> false) 
|> Seq.head 

我觉得这个方案是好的，因为它实现了一个更有用的功能可按，然后就用它来对解决您的具体问题三条线。