Использование кодов статуса 400
для любой другой цели, кроме указания неправильного запроса , является просто неправильным.
Если полезная нагрузка запроса содержит байтовую последовательность, которая может не анализируется как application/json
(если сервер ожидает, что dataformat), соответствующий код состояния 415
:
Сервер отказывается обслуживать запрос, поскольку объект запроса в формате, не поддерживаемом запрошенным ресурсом для запрошенного метода.
blockquote>Если полезная нагрузка запроса является синтаксически правильной, но семантически некорректной, может использоваться нестандартный
422
код ответа или стандартный403
код состояния:Сервер понял запрос, но отказывается его выполнять. Авторизация не поможет, и запрос НЕ ДОЛЖЕН повториться.
blockquote>
Если у вас есть массив из постоперационного обхода BST, вы знаете, что корень - последний элемент массива. Левый ребенок корня занимает первую часть массива и состоит из записей, меньших, чем корень. Затем следует правильный ребенок, состоящий из элементов, больших корня. (Оба ребенка могут быть пустыми).
________________________________
| | |R|
--------------------------------
left child right child root
Таким образом, основная проблема заключается в том, чтобы найти точку, в которой заканчивается левый ребенок, и начинается право.
Оба ребенка также получаются из их постоперационный ход, поэтому их построение производится таким же образом, рекурсивно.
BST fromPostOrder(value[] nodes) {
// No nodes, no tree
if (nodes == null) return null;
return recursiveFromPostOrder(nodes, 0, nodes.length - 1);
}
// Construct a BST from a segment of the nodes array
// That segment is assumed to be the post-order traversal of some subtree
private BST recursiveFromPostOrder(value[] nodes,
int leftIndex, int rightIndex) {
// Empty segment -> empty tree
if (rightIndex < leftIndex) return null;
// single node -> single element tree
if (rightIndex == leftIndex) return new BST(nodes[leftIndex]);
// It's a post-order traversal, so the root of the tree
// is in the last position
value rootval = nodes[rightIndex];
// Construct the root node, the left and right subtrees are then
// constructed in recursive calls, after finding their extent
BST root = new BST(rootval);
// It's supposed to be the post-order traversal of a BST, so
// * left child comes first
// * all values in the left child are smaller than the root value
// * all values in the right child are larger than the root value
// Hence we find the last index in the range [leftIndex .. rightIndex-1]
// that holds a value smaller than rootval
int leftLast = findLastSmaller(nodes, leftIndex, rightIndex-1, rootval);
// The left child occupies the segment [leftIndex .. leftLast]
// (may be empty) and that segment is the post-order traversal of it
root.left = recursiveFromPostOrder(nodes, leftIndex, leftLast);
// The right child occupies the segment [leftLast+1 .. rightIndex-1]
// (may be empty) and that segment is the post-order traversal of it
root.right = recursiveFromPostOrder(nodes, leftLast + 1, rightIndex-1);
// Both children constructed and linked to the root, done.
return root;
}
// find the last index of a value smaller than cut in a segment of the array
// using binary search
// supposes that the segment contains the concatenation of the post-order
// traversals of the left and right subtrees of a node with value cut,
// in particular, that the first (possibly empty) part of the segment contains
// only values < cut, and the second (possibly empty) part only values > cut
private int findLastSmaller(value[] nodes, int first, int last, value cut) {
// If the segment is empty, or the first value is larger than cut,
// by the assumptions, there is no value smaller than cut in the segment,
// return the position one before the start of the segment
if (last < first || nodes[first] > cut) return first - 1;
int low = first, high = last, mid;
// binary search for the last index of a value < cut
// invariants: nodes[low] < cut
// (since cut is the root value and a BST has no dupes)
// and nodes[high] > cut, or (nodes[high] < cut < nodes[high+1]), or
// nodes[high] < cut and high == last, the latter two cases mean that
// high is the last index in the segment holding a value < cut
while (low < high && nodes[high] > cut) {
// check the middle of the segment
// In the case high == low+1 and nodes[low] < cut < nodes[high]
// we'd make no progress if we chose mid = (low+high)/2, since that
// would then be mid = low, so we round the index up instead of down
mid = low + (high-low+1)/2;
// The choice of mid guarantees low < mid <= high, so whichever
// case applies, we will either set low to a strictly greater index
// or high to a strictly smaller one, hence we won't become stuck.
if (nodes[mid] > cut) {
// The last index of a value < cut is in the first half
// of the range under consideration, so reduce the upper
// limit of that. Since we excluded mid as a possible
// last index, the upper limit becomes mid-1
high = mid-1;
} else {
// nodes[mid] < cut, so the last index with a value < cut is
// in the range [mid .. high]
low = mid;
}
}
// now either low == high or nodes[high] < cut and high is the result
// in either case by the loop invariants
return high;
}
Вы действительно не нуждаетесь в обходном пути. Существует простой способ восстановить дерево, если только после обходного порядка:
Это легко можно сделать либо рекурсивно, либо итеративно с помощью стек, и вы можете использовать два индекса, чтобы указывать начало и конец текущего подматрица, а не фактически разделять массив.
Обход постопера выглядит следующим образом:
visit left
visit right
print current.
И так:
visit left
print current
visit right
Возьмем пример:
7
/ \
3 10
/ \ / \
2 5 9 12
/
11
Inorder is: 2 3 5 7 9 10 11 12
Postorder is: 2 5 3 9 11 12 10 7
Итерировать массив послепорядка в обратном порядке и продолжать разделять массив порядка, где это значение. Сделайте это рекурсивно, и это будет ваше дерево. Например:
current = 7, split inorder at 7: 2 3 5 | 9 10 11 12
Посмотрите знакомо? То, что слева, - это левое поддерево, а справа - правое поддерево, в псевдослучайном порядке по отношению к структуре BST. Однако теперь вы знаете, что такое ваш корень. Теперь сделаем то же самое для двух половинок. Найдите первое вхождение (с конца) элемента из левой половины в обход послепорядка. Это будет 3. Разделите вокруг 3:
current = 3, split inorder at 3: 2 | 5 ...
Итак, вы знаете, что ваше дерево выглядит так:
7
/
3
Это основано на фактах, что значение в обход послепорядка всегда появляется после появления его детей и что значение в обходном пути будет отображаться между его дочерними значениями.
Ничего не делайте. Последний элемент - ваш корень. затем, принимая массив назад, следуйте правилам вставки BST.
eg:-
given just the postorder -- 2 5 3 9 11 12 10 7
7
\
10
----
7
\
10
\
12
-----
7
\
10
\
12
/
11
-------
7
\
10
/ \
9 12
/
11
--------
7
/ \
3 10
/ \ / \
2 5 9 12
/
11