从数字序列构建一棵特殊的树

Question

我有一个有趣的任务，但我不知道如何解决它。

给定序列a=(a1,...,an)的无重复元素的最小二叉树M(a)定义如下： Be ai (a1,...,an)的最小个数),则M(a)的根为ai,其左子树为M(a1,...,ai-1),右子树为M(ai+1,...,an)。 M(∅) 是一棵空树。对于给定的序列，在 O(n) 中构造最小树。请注意，子树也是 M，因此它们必须遵循规则。

这里的例子。感谢您的帮助。

Answer 1

它叫做笛卡尔树。关于在此处创建一个的文章：https://iq.opengenus.org/cartesian-tree/

Answer 2

C:\Users\James\code\minbin>minbin
1 -> 2
2 -> 3
3 -> 7
3 -> 5
5 -> 11
5 -> 8
8 -> 15
8 -> 19
1 -> 12
12 -> 13

您可以在 https://gist.github.com/JamesBremner/ac9ad8db15eafaad57a89532e64ff7bf

查看生成此输出的代码

算法是递归的：

找到最小的元素
link parent 到最小
拆分剩余号码
如果左边是单个的，link 从最小的开始，否则再次调用 split
如果右边是单个的，link从最小的开始，否则再次调用split
return

从数字序列构建一棵特殊的树

Contructing a special tree, from numerical sequence

graph

binary-tree

theory