algorithm - 以特殊方式遍历树

Question

我们有一个二叉树

type 'a tree = Node of 'a * 'a tree * 'a tree | Null ;;

我们要返回一个“列表”，其中包含所有按特定顺序排列的顶点，即列表中两个相邻顶点之间的距离不能超过 3。每个顶点只能出现一次。

例子。对于树

      1
     / \
    2   6
   /
  3
 / \
4   5

一个可能的答案是[1; 3; 4; 5; 2; 6]

目前我有以下代码:

let walk t =
    let rec pom_walk t acc end_root = (* it's symmetric, so it could be start_root and the result would be correct too *)
        match t with
        | Null -> acc
        | Node (nr, l, r) ->
            if end_root then
                nr::(pom_walk r (pom_walk l acc false) false)
            else
                (pom_walk r (pom_walk l acc true) true) @ [nr]
     in
        pom_walk t [] true 

但由于使用了 @ 运算符，此代码具有平方复杂度，它本身是线性的。

我怎样才能在线性时间内解决这个问题？

Answer 1

因为您要将元素推送到列表的前面和 后面，所以能够轻松地执行这两个操作会很好。正如@david-eisenstat 建议的那样，您可以使用 difference lists .

我在这里提出一个不同的解决方案。我们将用两个列表表示我们的列表:一个初始段和一个(反向)结束段。

type 'a init_last = 'a list * 'a list

我们可以通过给出函数 to_list 使这种直觉更正式转动这样一个'a init_last进入'a list它代表:

let to_list (xs : 'a init_last) : 'a list =
  let (init, last) = xs in init @ rev last

现在很容易定义辅助函数来定义一个空的 'a init_last看起来像并将项目推到我们的 'a init_last 所代表的列表的顶部/末尾在恒定时间内:

let empty : 'a init_last = ([], [])

let push_top (a : 'a) (xs : 'a init_last) : 'a init_last =
  let (init, last) = xs in (a :: init, last)

let push_end (xs : 'a init_last) (a : 'a) : 'a init_last =
  let (init, last) = xs in (init, a :: last)

然后我们可以在您对 walk 的定义中使用这些组合器并返回一个更传统的 'a list通过后处理 pom_walk 的结果使用 to_list :

let walk t =
    let rec pom_walk t acc end_root =
        match t with
        | Null -> acc
        | Node (nr, l, r) ->
            if end_root then
                push_top nr (pom_walk r (pom_walk l acc false) false)
            else
                push_end (pom_walk r (pom_walk l acc true) true) nr
     in
        to_list (pom_walk t empty true)