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

Question

例如，我有一棵具有这种结构的树

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

我怎样才能得到最小深度的叶子？

Answer 1

解决这个问题的一种方法是实现广度优先搜索算法。该算法在“级别”中遍历一棵树，因此它返回根，然后是根的所有孩子，然后是这些孩子的所有孩子，依此类推。您可以将其写为 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

我认为这个解决方案很好，因为它实现了一个更有用的功能，然后用它在三行上解决您的特定问题。

Answer 2

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