返回信息流最近为了准备考试一直在写百练，但是发现Java在读入的时候时间好像有点长……
今天又写到一道题：
[4079:二叉搜索树](http://bailian.openjudge.cn/practice/4079/)
### 描述
二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。
这里，我们想探究二叉树的建立和序列输出。
### 输入
只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复）
### 输出
输出一行，对输入数字建立二叉搜索树后进行前序周游的结果。
### 样例输入
41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 942 827 436
### 样例输出
41 467 334 169 145 281 358 464 436 500 478 491 724 705 962 827 961 942 995
代码如下：
```
import java.util.*;
import java.lang.*;
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val = val;
this.left = null;
this.right = null;
}
}
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
TreeNode root = new TreeNode(sc.nextInt());
while(sc.hasNextInt()){
int temp = sc.nextInt();
build(root, temp);
}
display(root);
System.out.println();
sc.close();
}
public static void build(TreeNode node, int val){
if(val < node.val){
if(node.left == null){
node.left = new TreeNode(val);
}
else{
build(node.left, val);
}
}
else if(val > node.val){
if(node.right == null){
node.right = new TreeNode(val);
}
else{
build(node.right, val);
}
}
}
public static void display(TreeNode node){
if(node != null){
System.out.print(String.valueOf(node.val) + " ");
display(node.left);
display(node.right);
}
}
}
```
尝试修改多次，一直是TLE，不是很理解……
求教哪里写的不对……
因为Eclipse自己设计了一些实例都是可以完成的
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91080同步于 2016/9/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
求教建立二叉搜索树的一道题，一直是TLE
Thesharing
2016/9/16镜像同步11 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 kit 的大作中提到: 】
: 题目说数字有重复。
谢谢~ 不过在`public static void build(TreeNode node, int val)` 里面 如果val == node.val的话应该会直接返回 那么相当于没有加到树里直接处理下一个了……
用C++重新实现了一下，代码如下：
```
#include <iostream>
using namespace std;
class TreeNode{
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val){
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
void build(TreeNode* node, int val){
if(val < node->val){
if(!node->left){
node->left = new TreeNode(val);
}
else{
build(node->left, val);
}
}
else if(val > node->val){
if(!node->right){
node->right = new TreeNode(val);
}
else{
build(node->right, val);
}
}
}
void display(TreeNode* node){
if(node){
cout << node->val << " ";
display(node->left);
display(node->right);
}
}
int main(void){
int temp = 0;
cin >> temp;
TreeNode * root = new TreeNode(temp);
while(cin >> temp){
build(root, temp);
}
display(root);
cout << endl;
}
```
结果是AC。
现在问题是，是不是OJ对Java的支持比较差，还是读入、输出成为了瓶颈……？
呀，我猜如果不是写法有问题的话就是输入输出的问题啦。java的输入输出还是挺慢的。
另，我猜测还是写法问题，总不可能别人java都不过吧
【 在 Thesharing 的大作中提到: 】
: [md]
: 用C++重新实现了一下，代码如下：
: ```
: ...................
其实这题很烂
为啥这么说呢
建立BST的方法不只一个，只要满足BST的条件，那么我建立的树就是正确的。
但是由此产生的preorder/postorder序列又是不一样的。
呵呵。
【 在 whn6325689 的大作中提到: 】
: 呀，我猜如果不是写法有问题的话就是输入输出的问题啦。java的输入输出还是挺慢的。
: 另，我猜测还是写法问题，总不可能别人java都不过吧
谢谢~ 不过C++版本直接过了…… 是复杂度比较高的原因吗，导致C++可以过而Java不能过？
我猜可能是Java的写法有一些小问题，导致常数过高。
一般情况下Java读入确实比较慢，可以写一个读入挂
【 在 Thesharing 的大作中提到: 】
:
: 谢谢~ 不过C++版本直接过了…… 是复杂度比较高的原因吗，导致C++可以过而Java不能过？
【 在 whn6325689 的大作中提到: 】
: 我猜可能是Java的写法有一些小问题，导致常数过高。
: 一般情况下Java读入确实比较慢，可以写一个读入挂
常数过高指的是……？希望能细讲一点，先在此谢过Otz
此外，读入挂是指这个吗?
```java
public static void main(String[] args)throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int ans = (int)in.nval;
// ......
out.println(ans);
out.flush();
}
```
当时尝试用了，但是仍然是TLE（上图中5次TLE中的最后两次）……
不是读写问题。算法的锅
class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(String fileName) {
try {
br = new BufferedReader(new FileReader(fileName));
} catch (FileNotFoundException e) {
}
}
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(nextToken());
}
long nextLong() {
return Long.parseLong(nextToken());
}
double nextDouble() {
return Double.parseDouble(nextToken());
}
}
【 在 Thesharing 的大作中提到: 】
:
: 常数过高指的是……？希望能细讲一点，先在此谢过Otz
: 此外，读入挂是指这个吗?
: ...................