以特殊的方式遍历树

我们有一个二叉树以特殊的方式遍历树

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

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

例子。对于树

一个可能的答案是[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

但是这个代码有方形的复杂性，由于@操作者的使用，这本身就是线性的。

如何在线性时间内解决这个问题？

来源

2015-11-24 marmistrz

你的“可能的答案”是错误的，6 - 2 = 4 –

@willywonka_dailyblah在图中距离为2 – btilly

不熟悉OCaml的，但我猜测'@'是list append？在Haskell中，一种常用的方法是从列表切换到将列表添加到其输入的函数，以便您可以有效地在两端使用连接（=函数合成）。 –

因为您正在推动列表后面的和上的元素，所以能够轻松地执行这两个操作会很好。正如@ 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定义中使用这些组合程序和后处理的pom_walk结果使用to_list返回一个更传统的'a 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)

来源

2015-11-25 13:21:37 gallais

@gallais表现出了很好的解决方案，我想与大家分享我想出的那个。请仔细检查它，直到有一无所有的;）

let walk t = 
    let rec pom_walk t cont end_root = 
     match t with 
     | Null -> cont 
     | Node (nr, l, r) -> 
      let resL = pom_walk l cont (not end_root) in 
      let resR = pom_walk r resL (not end_root) in 
       if end_root then 
        function res -> nr::(resR res) 
       else 
        function res -> resR (nr::res) 
    in 
     pom_walk t (fun x -> x) true []

来源

2015-11-25 15:33:02 marmistrz

以特殊的方式遍历树

回答

相关问题