Jin
BAN USERForgot something.
private static class Bound {
int start;
int center;
int end;
public Bound(final int start, final int center, final int end) {
this.start = start;
this.center = center;
this.end = end;
}
public boolean inTheLeft(int pos) {
return pos >= start && pos < center;
}
public boolean inTheRight(int pos) {
return pos >= center && pos < end;
}
public boolean onTheLeft(int pos) {
return pos == start;
// || pos == (end - 1)
}
}
A bit wordy, but it works.
public static TreeNode<Integer> nonRecursReverseTree(Integer[] inOrder, Integer[] preOrder) {
final Stack<TreeNode<Integer>> treeStack = new Stack<TreeNode<Integer>>();
final Stack<Bound> bounds = new Stack<Bound>();
TreeNode<Integer> prevNode = new TreeNode<Integer>(preOrder[0]);
final TreeNode<Integer> result = prevNode;
int nodePos = Arrays.binarySearch(inOrder, 0, preOrder.length, preOrder[0]);
Bound prevBound = new Bound(0, nodePos, preOrder.length);
treeStack.push(prevNode);
bounds.push(prevBound);
int cnt = 2;
int prePosition = 1;
while (prePosition < preOrder.length) {
nodePos = Arrays.binarySearch(inOrder, prevBound.start, prevBound.end, preOrder[prePosition]);
cnt++;
if (nodePos >= 0) {
final TreeNode<Integer> curNode = new TreeNode<Integer>(preOrder[prePosition]);
final Bound curBound;
if (prevBound.inTheLeft(nodePos)) {
prevNode.left = curNode;
curBound = new Bound(prevBound.start, nodePos, prevBound.center);
} else {
prevNode.right = curNode;
curBound = new Bound(prevBound.center, nodePos, prevBound.end);
}
if (prevBound.onTheLeft(nodePos)) {
prevBound = bounds.pop();
prevNode = treeStack.pop();
} else {
treeStack.push(curNode);
bounds.push(curBound);
prevBound = curBound;
prevNode = curNode;
}
prePosition++;
} else {
prevBound = bounds.pop();
prevNode = treeStack.pop();
}
}
System.out.println("cnt = " + cnt);
return result;
}
I can be wrong, but it looks very similar to the clustering problem. This algorithm might be used here - en.wikipedia.org/wiki/K-means_clustering
- Jin September 06, 2013