Eli Bendersky's website OK, I solved ACM problem 1136 from USU's site(solution submitted and accepted). Here goes:
A postorder indeed uniquely defines a BST. I'm almost 100% sure - I have a totally deterministic algorithm (no choice whatsoever) that builds a BST from its postorder, but I can't prove the uniqueness formally. Never mind...
The algorithm goes as follows:
* vec: global stack of postorder numbers
* node is a BST node, contains a number,
and left & right pointers
* a window is a pair of numbers (L, R)
build_node (node, window)
if vec is empty
return END
next = next number on stack
if next is in the window
pop the vec stack by 1
new_node = new node(next)
if next > node->num
node-&g;tright = new_node
new_window = (node->num, window->R)
eles
node->left = new_node
new_window = (window->L, node->num)
status = build_node(new_node, new_window)
if status = END
return END
else if status = NOT_IN_LIMIT
return build_node(node, window)
else
return NOT_IN_LIMIT
return OK
The idea is simple: in postorder, the last element is the root. The one before last is its son. Which son ? Depending on ordering. If it's larger than the root, right son, otherwise left son. And so we can descend recursively deep into the tree. But what happens once, say, the right line ends and the left descendant of the root appears ? We should backtrack back to the root and take left. So, "window" is used for this purpose. At each point we keep track of what values are legal. If a value out of the window is met, we backtrack.
I implemented it in C++, using deque