Код:
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class Solution {
static BufferedWriter out;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new File("tst.in"));
out = new BufferedWriter(new FileWriter("tst.out"));
Tree tr = new Tree();
int n = 0;
while (in.hasNext()) {
tr.insert(in.nextInt());
n++;
}
if (n==0) {
out.close();
return;
}
tr.finalSolve();
out.close();
}
static class Tree {
static class Node {
public Node left, right;
public int key;
public Node(int x) {
this.key = x;
}
}
public Node root;
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
int min=-1;
int count = -1;
public Tree() {
root = null;
}
public Tree(int x) {
root.left = null;
root.right = null;
root.key = x;
}
public void insert(int val) {
Node x = root;
Node y = null;
while (x != null) {
y = x;
if (x.key > val)
x = x.left;
else
x = x.right;
}
Node newNode = new Node(val);
if (y == null) {
root = newNode;
} else if (newNode.key < y.key) {
y.left = newNode;
} else
y.right = newNode;
}
public void delete(int value) {
Node x = root;
Node y = null;
while (x != null) {
if (x.key == value)
break;
y = x;
if (x.key > value)
x = x.left;
else
x = x.right;
}
if (x == null)
return;
if (x.left == null) {
if (y == null)
root = x.right;
else {
if (y.left == x)
y.left = x.right;
else
y.right = x.right;
}
}
else if (x.right==null) {
if (y==null)
root = x.left;
else {
if (y.left == x)
y.left = x.left;
else
y.right = x.left;
}
}
else {
Node z = x.left;
y = null;
while (z.right != null) {
y = z;
z = z.right;
}
if (y != null)
y.right = z.left;
else
x.left = z.left;
x.key = z.key;
}
}
private void show(Node a) throws IOException {
out.append(Integer.toString(a.key));
out.append('\n');
}
private void bypass(Node x) throws IOException {
if (x==null)
return;
show(x);
bypass(x.left);
bypass(x.right);
}
public void show_ans() throws IOException{
bypass(root);
}
public void findMinPath() {
find(root);
}
private void find(Node x) {
if (x==null)
return;
count++;
if ((x.left==null)&&(x.right==null)&&((count < min)||(min==-1))) {
min = count;
//System.out.println(x.key);
}
find(x.left);
find(x.right);
count--;
}
private void findNodes() {
findMinPath();
if (min%2 != 0)
return;
solve(root);
}
private void solve(Node x) {
if (x==null)
return;
left.add(x.key);
solve(x.left);
left.remove(left.size()-1);
right.add(x.key);
solve(x.right);
right.remove(right.size()-1);
if ((x.left==null)&&(x.right==null)) {
if (min == left.size()+right.size()) {
left.add(x.key);
int k = ((left.size()-1)+(right.size()-1))/2 + 1;
if (k < left.size())
res.add(left.get(k));
else
{
k -= (left.size()-1);
res.add(right.get(right.size()-k));
}
left.remove(left.size()-1);
}
}
}
public void finalSolve() throws IOException {
findNodes();
for(int x : res) {
delete(x);
}
show_ans();
}
}
}
В общем эта программа на различных тестах ест около 460МБ, что естественно очень много. Сама программа состоит в том, что я строю 2ичное дерево поиска и потом удаляя на всех путях минимальной длины от корня до листа вершину среднюю по значению. Но я не могу за счёт чего идут такие расходы памяти. Вроде бы я нигде не складываю строк в цикле. Возможно ли то что класс вершин дерева у меня статический как-то сразу выделяет много памяти и поэтому её не хватает? Подскажите почему может так расходоваться память.