Reconstruct a BST from traversal data
RebuildBSTPreorder.javapublic static <T extends Comparable<T>> BinaryTree<T> rebuildBSTFromPreorder(
List<T> preorder) {
return rebuildBSTFromPreorderHelper(preorder, 0, preorder.size());
}
// Build a BST based on preorder[s : e - 1], return its root.
private static <T extends Comparable<T>> BinaryTree<T>
rebuildBSTFromPreorderHelper(List<T> preorder, int s, int e) {
if (s < e) {
int x = s + 1;
while (x < e && preorder.get(x).compareTo(preorder.get(s)) < 0) {
++x;
}
return new BinaryTree<>(preorder.get(s), rebuildBSTFromPreorderHelper(
preorder, s + 1, x), rebuildBSTFromPreorderHelper(preorder, x, e));
}
return null;
}
RebuildBSTPreorderBetter.java
private static Integer idx;
public static BinaryTree<Integer> rebuildBSTFromPreorder(
List<Integer> preorder) {
idx = 0;
return rebuildBSFromPreorderHelper(preorder,
Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private static BinaryTree<Integer> rebuildBSFromPreorderHelper(
List<Integer> preorder, Integer min, Integer max) {
if (idx == preorder.size()) {
return null;
}
Integer curr = preorder.get(idx);
if (curr < min || curr > max) {
return null;
}
++idx;
return new BinaryTree<>(
curr,
rebuildBSFromPreorderHelper(preorder, min, curr),
rebuildBSFromPreorderHelper(preorder, curr, max));
}
