View difference between Paste ID: gnJ1PVUK and

-
+Условие
 Найти пути минимальной длины между корнем и листьями и удалить средние по значению вершины этих путей (левым удалением), если они существуют .
 Замечание.
 Если некоторая вершина является средней по значению для нескольких путей минимальной длины, то удаляется она только один раз.(см. Пример 2).
 
 
 Входные данные
 tst.in содержит последовательность чисел — ключей дерева.
 
 Выходные данные
 tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева.
 
 Пример
 tst.in
 10
 15
 13
 18
 5
 8
 3
 
 tst.out
 10
 3
 18
 
 
 import java.io.*;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.TreeSet;
 
 import static java.lang.System.out;
 
 /**
  * Created by IntelliJ IDEA.
  * User: Andrew
  * Date: 12.02.2011
  * Time: 19:53:21
  * To change this template use File | Settings | File Templates.
  */
 
 
 public class Solution {
 	interface Position {
 		public int element();
 	}
 
 	static class LinkedBinaryTree {
 		public void setMinLen(int minLen) {
 			this.minLen = minLen;
 		}
 
 		public void setCurLen(int curLen) {
 			this.curLen = curLen;
 		}
 
 		public ArrayList<Integer> arrayOfLeafs = new ArrayList<Integer>();
 		public int minLen;
 		public int curLen;
 
 		class BTNode implements Position {
 			private int element;
 			private BTNode left, right;
 
 			public BTNode(int el, BTNode l, BTNode r) {
 				setElement(el);
 				setLeft(l);
 				setRight(r);
 			}
 
 			public int element() {
 				return element;
 			}
 
 			public void setElement(int el) {
 				element = el;
 			}
 
 			public BTNode getLeft() {
 				return left;
 			}
 
 			public void setLeft(BTNode v) {
 				left = v;
 			}
 
 			public BTNode getRight() {
 				return right;
 			}
 
 			public void setRight(BTNode v) {
 				right = v;
 			}
 		}
 
 		private Position root; // reference to the root
 		private int size; // number of nodes
 
 		public LinkedBinaryTree() {
 			root = null;
 			size = 0;
 		}
 
 		public LinkedBinaryTree(int rootEl) {
 			root = new BTNode(rootEl, null, null);
 			size = 1;
 		}
 
 		public int size() {
 			return size;
 		}
 
 		public boolean isEmpty() {
 			return (size == 0);
 		}
 
 		public boolean isExternalLeft(Position v) {
 			return (((BTNode) v).getLeft() == null);
 		}
 
 		public boolean isExternalRight(Position v) {
 			return (((BTNode) v).getRight() == null);
 		}
 
 		public boolean isRoot(Position v) {
 			return (v == root());
 		}
 
 		public Position root() {
 			return root;
 		}
 
 		public Position leftChild(Position v) {
 			return ((BTNode) v).getLeft();
 		}
 
 		public Position rightChild(Position v) {
 			return ((BTNode) v).getRight();
 		}
 
 		private int setElement(Position v, int o) {
 			int temp = ((BTNode) v).element();
 			((BTNode) v).setElement(o);
 			return temp;
 		}
 
 		private void expandExternalLeft(Position v) {
 			if (isExternalLeft(v)) {
 				((BTNode) v).setLeft(new BTNode(0, null, null));
 				size++;
 			}
 		}
 
 		private void expandExternalRight(Position v) {
 			if (isExternalRight(v)) {
 				((BTNode) v).setRight(new BTNode(0, null, null));
 				size++;
 			}
 		}
 
 		private void addElementFromRoot(Position pos, int el) {
 			if (pos != null) {
 				if (pos.element() == el)
 					return;
 				else {
 					if (pos.element() < el) {
 						if (isExternalRight(pos)) {
 							expandExternalRight(pos);
 							setElement(rightChild(pos), el);
 						} else {
 							addElementFromRoot(rightChild(pos), el);
 						}
 					} else {
 						if (pos.element() > el) {
 							if (isExternalLeft(pos)) {
 								expandExternalLeft(pos);
 								setElement(leftChild(pos), el);
 							} else {
 								addElementFromRoot(leftChild(pos), el);
 							}
 						}
 					}
 				}
 			} else {
 				root = new BTNode(el, null, null);
 				size++;
 			}
 		}
 
 
 		private void rootLeftRightFromRoot(Position pos, StringBuilder outString) {
 			if (pos == null) {
 				return;
 			}
 			outString.append(pos.element()+"\r\n");
 			if (leftChild(pos) != null)
 				rootLeftRightFromRoot(leftChild(pos), outString);
 			if (rightChild(pos) != null)
 				rootLeftRightFromRoot(rightChild(pos), outString);
 		}
 
 
 		public void addElement(int el) {
 			addElementFromRoot(root(), el);
 		}
 
 		public void deleteElement(int el) {
 			Position x = root, y = null;
 
 			while (x != null) {
 				if (el == x.element()) {
 					break;
 				} else {
 					y = x;
 					if (el < x.element()) {
 						x = ((BTNode) x).getLeft();
 					} else {
 						x = ((BTNode) x).getRight();
 					}
 				}
 
 			}
 
 			if (x == null)
 				return;
 
 			if (((BTNode) x).getLeft() == null) {
 				if (y == null) {
 					root = ((BTNode) x).getLeft();
 				} else {
 					if (x == ((BTNode) y).getRight()) {
 						((BTNode) y).setRight(((BTNode) x).getRight());
 					} else {
 						((BTNode) y).setLeft(((BTNode) x).getRight());
 					}
 				}
 			} else {
 				Position leftMost = ((BTNode) x).getLeft();
 				y = null;
 				while (((BTNode) leftMost).getRight() != null) {
 					y = leftMost;
 					leftMost = ((BTNode) leftMost).getRight();
 				}
 				if (y != null) {
 					((BTNode) y).setRight(((BTNode) leftMost).getLeft());
 				} else {
 					((BTNode) x).setLeft(((BTNode) leftMost).getLeft());
 				}
 				((BTNode) x).setElement((leftMost).element());
 			}
 		}
 
 		public void rootLeftRight(String path) throws IOException {
 			FileOutputStream fos = new FileOutputStream(path);
 			DataOutputStream dos = new DataOutputStream(fos);
 			StringBuilder temp = new StringBuilder();
 
 			rootLeftRightFromRoot(root(), temp);
 
 			dos.writeBytes(temp.toString());
 
 		}
 
 		public void assistRootLeftRight(Position pos) {
 			if (pos == null) {
 				return;
 			}
 
 			curLen++;
 			if (rightChild(pos) == null && leftChild(pos) == null) {
 				if (curLen == minLen) {
 					arrayOfLeafs.add(pos.element());
 				}
 				if (curLen < minLen) {
 					minLen = curLen;
 					arrayOfLeafs.clear();
 					arrayOfLeafs.add(pos.element());
 				}
 			}
 			if (leftChild(pos) != null) {
 				assistRootLeftRight(leftChild(pos));
 			}
 			if (rightChild(pos) != null) {
 				assistRootLeftRight(rightChild(pos));
 			}
 
 			curLen--;
 
 		}
 
 		public void findAndDeleteElements() {
 			if (minLen % 2 != 0) {
 				TreeSet<Integer> setOfNodesToDelete = new TreeSet<Integer>();
 				for (Integer li : arrayOfLeafs) {
 					Position pos = root;
 					ArrayList<Integer> tempArray = new ArrayList<Integer>();
 
 					while (li != pos.element()) {
 						tempArray.add(pos.element());
 						if (li > pos.element())
 							pos = ((BTNode) pos).getRight();
 						else if (li < pos.element()) {
 							pos = ((BTNode) pos).getLeft();
 						}
 					}
 					tempArray.add(li);
 
 					Collections.sort(tempArray);
 					setOfNodesToDelete.add(tempArray.get(minLen / 2));
 				}
 
 				for (Integer li : setOfNodesToDelete) {
 					this.deleteElement(li);
 				}
 			}
 		}
 	}
 	public static void main(String[] args) {
 
 		LinkedBinaryTree tree = new LinkedBinaryTree();
 
 		FileInputStream fis = null;
 		try {
 			fis = new FileInputStream("tst.in");
 			BufferedReader br = new BufferedReader(new InputStreamReader(fis));
 			String newLine;
 			while ((newLine = br.readLine()) != null){
 				tree.addElement(Integer.parseInt(newLine));
 			}
 
 			tree.setCurLen(0);
 			tree.setMinLen(tree.size());
 
 			tree.assistRootLeftRight(tree.root());
 			tree.findAndDeleteElements();
 			tree.rootLeftRight("tst.out");
 
 
 		} catch (FileNotFoundException e) {
 			out.println("No Such File");  //To change body of catch statement use File | Settings | File Templates.
 		} catch (IOException e) {
 			out.println("File Exception");  //To change body of catch statement use File | Settings | File Templates.
 		}
 	}
 }