如何获得深度最小的叶子

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