import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.TreeMap;
class Treverse {
private static final class ColumnFind<U> {
private final int column;
private final Node<U> node;
public ColumnFind(int column, Node<U> node) {
super();
this.column = column;
this.node = node;
}
}
private static final class Node<T> {
private Node<T> left, right;
private final T value;
public Node(T value, Node<T> left, Node<T> right) {
super();
this.value = value;
this.left = left;
this.right = right;
}
public Node<T> left() {
return left;
}
public Node<T> right() {
return right;
}
@Override
}
}
public static final <N> void traverse(Node<N> root) {
final TreeMap
<Integer, List
<Node
<N
>>> columnMap
= new TreeMap
<>(); final Queue<ColumnFind<N>> queue = new LinkedList<>();
queueChild(0, root, queue);
while (!queue.isEmpty()) {
ColumnFind<N> cf = queue.remove();
int column = cf.column;
Node<N> node = cf.node;
columnMap.computeIfAbsent(column, c -> new ArrayList<>()).add(node);
queueChild(column - 1, node.left(), queue);
queueChild(column + 1, node.right(), queue);
}
for (Entry
<Integer, List
<Node
<N
>>> entry
: columnMap.
entrySet()) { System.
out.
println("Column - " + entry.
getKey() + " : " + entry.
getValue()); }
}
private static final <N> void queueChild(int column, Node<N> node, Queue<ColumnFind<N>> queue) {
if (node == null) {
return;
}
queue.add(new ColumnFind<>(column, node));
}
public static void main
(String[] args
) { Node<Integer> five = new Node<>(5, null, null);
Node<Integer> four = new Node<>(4, null, five);
Node<Integer> three = new Node<>(3, null, null);
Node<Integer> two = new Node<>(2, null, four);
Node<Integer> one = new Node<>(1, two, three);
traverse(one);
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlua2VkTGlzdDsKaW1wb3J0IGphdmEudXRpbC5MaXN0OwppbXBvcnQgamF2YS51dGlsLk1hcC5FbnRyeTsKaW1wb3J0IGphdmEudXRpbC5RdWV1ZTsKaW1wb3J0IGphdmEudXRpbC5UcmVlTWFwOwoKCmNsYXNzIFRyZXZlcnNlIHsKICAgIAogICAgcHJpdmF0ZSBzdGF0aWMgZmluYWwgY2xhc3MgQ29sdW1uRmluZDxVPiB7CiAgICAgICAgcHJpdmF0ZSBmaW5hbCBpbnQgY29sdW1uOwogICAgICAgIHByaXZhdGUgZmluYWwgTm9kZTxVPiBub2RlOwogICAgICAgIAogICAgICAgIHB1YmxpYyBDb2x1bW5GaW5kKGludCBjb2x1bW4sIE5vZGU8VT4gbm9kZSkgewogICAgICAgICAgICBzdXBlcigpOwogICAgICAgICAgICB0aGlzLmNvbHVtbiA9IGNvbHVtbjsKICAgICAgICAgICAgdGhpcy5ub2RlID0gbm9kZTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgCiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIGZpbmFsIGNsYXNzIE5vZGU8VD4gewogICAgICAgIAogICAgICAgIHByaXZhdGUgTm9kZTxUPiBsZWZ0LCByaWdodDsKICAgICAgICBwcml2YXRlIGZpbmFsIFQgdmFsdWU7CiAgICAgICAgCiAgICAgICAgcHVibGljIE5vZGUoVCB2YWx1ZSwgTm9kZTxUPiBsZWZ0LCBOb2RlPFQ+IHJpZ2h0KSB7CiAgICAgICAgICAgIHN1cGVyKCk7CiAgICAgICAgICAgIHRoaXMudmFsdWUgPSB2YWx1ZTsKICAgICAgICAgICAgdGhpcy5sZWZ0ID0gbGVmdDsKICAgICAgICAgICAgdGhpcy5yaWdodCA9IHJpZ2h0OwogICAgICAgIH0KCiAgICAgICAgcHVibGljIE5vZGU8VD4gbGVmdCgpIHsKICAgICAgICAgICAgcmV0dXJuIGxlZnQ7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgTm9kZTxUPiByaWdodCgpIHsKICAgICAgICAgICAgcmV0dXJuIHJpZ2h0OwogICAgICAgIH0KICAgICAgICAKICAgICAgICBAT3ZlcnJpZGUKICAgICAgICBwdWJsaWMgU3RyaW5nIHRvU3RyaW5nKCkgewogICAgICAgICAgICByZXR1cm4gU3RyaW5nLnZhbHVlT2YodmFsdWUpOwogICAgICAgIH0KICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyBmaW5hbCA8Tj4gdm9pZCB0cmF2ZXJzZShOb2RlPE4+IHJvb3QpIHsKICAgICAgICAKICAgICAgICBmaW5hbCBUcmVlTWFwPEludGVnZXIsIExpc3Q8Tm9kZTxOPj4+IGNvbHVtbk1hcCA9IG5ldyBUcmVlTWFwPD4oKTsKICAgICAgICBmaW5hbCBRdWV1ZTxDb2x1bW5GaW5kPE4+PiBxdWV1ZSA9IG5ldyBMaW5rZWRMaXN0PD4oKTsKICAgICAgICAKICAgICAgICBxdWV1ZUNoaWxkKDAsIHJvb3QsIHF1ZXVlKTsKICAgICAgICAKICAgICAgICB3aGlsZSAoIXF1ZXVlLmlzRW1wdHkoKSkgewogICAgICAgICAgICBDb2x1bW5GaW5kPE4+IGNmID0gcXVldWUucmVtb3ZlKCk7CiAgICAgICAgICAgIGludCBjb2x1bW4gPSBjZi5jb2x1bW47CiAgICAgICAgICAgIE5vZGU8Tj4gbm9kZSA9IGNmLm5vZGU7CiAgICAgICAgICAgIGNvbHVtbk1hcC5jb21wdXRlSWZBYnNlbnQoY29sdW1uLCBjIC0+IG5ldyBBcnJheUxpc3Q8PigpKS5hZGQobm9kZSk7CiAgICAgICAgICAgIHF1ZXVlQ2hpbGQoY29sdW1uIC0gMSwgbm9kZS5sZWZ0KCksIHF1ZXVlKTsKICAgICAgICAgICAgcXVldWVDaGlsZChjb2x1bW4gKyAxLCBub2RlLnJpZ2h0KCksIHF1ZXVlKTsKICAgICAgICB9CgogICAgICAgIGZvciAoRW50cnk8SW50ZWdlciwgTGlzdDxOb2RlPE4+Pj4gZW50cnk6IGNvbHVtbk1hcC5lbnRyeVNldCgpKSB7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiQ29sdW1uIC0gIiArIGVudHJ5LmdldEtleSgpICsgIiA6ICIgKyBlbnRyeS5nZXRWYWx1ZSgpKTsKICAgICAgICB9CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIGZpbmFsIDxOPiB2b2lkIHF1ZXVlQ2hpbGQoaW50IGNvbHVtbiwgTm9kZTxOPiBub2RlLCBRdWV1ZTxDb2x1bW5GaW5kPE4+PiBxdWV1ZSkgewogICAgICAgIGlmIChub2RlID09IG51bGwpIHsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBxdWV1ZS5hZGQobmV3IENvbHVtbkZpbmQ8Pihjb2x1bW4sIG5vZGUpKTsKICAgIH0KICAgIAogICAgCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgTm9kZTxJbnRlZ2VyPiBmaXZlID0gbmV3IE5vZGU8Pig1LCBudWxsLCBudWxsKTsKICAgICAgICBOb2RlPEludGVnZXI+IGZvdXIgPSBuZXcgTm9kZTw+KDQsIG51bGwsIGZpdmUpOwogICAgICAgIE5vZGU8SW50ZWdlcj4gdGhyZWUgPSBuZXcgTm9kZTw+KDMsIG51bGwsIG51bGwpOwogICAgICAgIE5vZGU8SW50ZWdlcj4gdHdvID0gbmV3IE5vZGU8PigyLCBudWxsLCBmb3VyKTsKICAgICAgICBOb2RlPEludGVnZXI+IG9uZSA9IG5ldyBOb2RlPD4oMSwgdHdvLCB0aHJlZSk7CiAgICAgICAgdHJhdmVyc2Uob25lKTsKICAgIH0KCn0K