源码

algorithm – 排序列表以完成BST数组表示


我想知道在排序的数组(例如,[1,2,3,4,5,6])和当从这个排序的数组构造完整的二进制搜索树时获得的表示之间是否存在映射,并且将所述二叉搜索树表示为数组(例如,[4,2,6,1,3,5],见下图)?

     4
  2     6
1   3  5

这里有一些更多的上下文:众所周知,人们可以从中获取一个有序数组并从中构造一个完整的二进制搜索树(有一个唯一的表示).递归算法是:找到合适的mid(这实际上非常棘手),然后将其视为根
递归左子阵和右子阵.从生成的BST中,可以执行水平顺序遍历(基本上是广度优先搜索)来构造完整BST的数组表示.

我问这个的原因是这个映射与数组的内容无关:它只取决于它的长度.因此,我感觉应该可以将两个数组简洁地表达为彼此的函数.

有什么想法吗?

(0)

本文由 投稿者 创作,文章地址:https://blog.isoyu.com/archives/algorithm-paixuliebiaoyiwanchengbstshuzubiaoshi.html
采用知识共享署名4.0 国际许可协议进行许可。除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。最后编辑时间为:11月 11, 2019 at 12:40 下午

热评文章