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

## Comments

comments powered by Disqus