自定义二进制搜索树中的最短路径

这是编码竞赛中的一个问题

最初的问题可以在这里找到http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf 问题5

通过霍尔的最短路径[由Hulsbos High的Alan Smithee撰写]

大厅墙上有一排排的椅子,但每排都有两把椅子丢失.每行中的椅子都有1到100的数字.编写一个程序,计算从大厅前面到后面的最短路径的长度.每把椅子宽1个单位,每排深1个单位(从椅子前面到椅子前面).对角线移动是不可能的.您可以从前排的任何间隙开始,并在最后一行的任何间隙后面结束.你总是走在间隙的中间.插图是通过大厅的最短路径,有五排椅子.在图示中,大厅只有10个椅子而不是100个.输入中的第一个数字将包含数字n - 行数.接下来的n行将有两个数字,用空格分隔,表示间隙的位置.输入示例:5 3 6 2 8 4 5 7 8 3 10

我认为我有一个有效的算法,我认为它会起作用,但我不确定如何将它实现到Java中.

我想要做的是将每个选项分解为搜索树,例如,如果用户输入是:

行数:3

空间:4 7 2 9 8 11

制作2个搜索树:

              4                               7            
       2           9                     2           9
     8   11      8   11             8      11     8      11

Run Code Online (Sandbox Code Playgroud)

然后找到每个节点之间差异最小的路径所以在这种情况下,最短路径将在第二个树7-> 9-> 8中,总距离为5(|| 7-9 | -8 |那么我的问题是