本文主要是介绍数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Tree Construction Problem's Link
----------------------------------------------------------------------------
Mean:
给定n个数，按照构造Binary Search Tree的方式来构造BST树，按顺序输出每一个非root结点的父节点的值。
analyse:
构造BST树最坏情况下时间复杂度为O(n)，肯定会超时。
注意到只需要输出结点的父节点的值，不需要真的构造BST树。
插到第i个结点时，我们在前i-1个结点中找两个数，一个是比Ai大的最小数，一个是比Ai小的最大数。
那么Ai的父节点肯定是这两个中的一个，到底是哪一个呢，根据画图分析，可以得出是后来插入的那个。
如下图所示：
做法：用java里面的容器TreeMap<Integer,Integer>来存储<value,index>对，根据value值来查找，然后比较这两个数的index大小来判断谁是父节点。
Time complexity: O(n*logn)
view code
import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main( String [] argv ){
Scanner in = new Scanner( new BufferedInputStream( System . in));
while( in . hasNext ()){
int n = in . nextInt();
TreeSet < Integer > vals = new TreeSet <>();
HashMap < Integer , Integer > idx = new HashMap <>();
int val = in . nextInt();
vals . add( val);
idx . put( val , 0);
for( int i = 1; i <n ;++ i ){
val = in . nextInt();
Integer hi = vals . higher( val ), lo = vals . lower( val);
if( hi == null)
System . out . print( lo + " ");
else if( lo == null)
System . out . print( hi + " ");
else {
Integer hiIdx = idx . get( hi);
Integer loIdx = idx . get( lo);
if( hiIdx > loIdx)
System . out . print( hi + " ");
else
System . out . print( lo + " ");
}
vals . add( val);
idx . put( val , i);
}
System . out . println();
}
}
}
这篇关于数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
