Жишээ тэстүүд

Оролт
3 2
1 2 LEFT
1 3 RIGHT

Гаралт
2 1 3

Оролт
3 2
1 2 RIGHT
1 3 LEFT

Гаралт
IMPOSSIBLE


Тэмдэглэл

Consider the first sample test. We need to find a tree with 3 nodes that satisfies the following two constraints. The node labeled 2 with pre-order traversal should be in the left subtree of the node labeled 1 with pre-order traversal; the node labeled 3 with pre-order traversal should be in the right subtree of the node labeled 1. There is only one tree with three nodes that satisfies these constraints and its in-order traversal is (2, 1, 3).

Pre-order is the "root – left subtree – right subtree" order. In-order is the "left subtree – root – right subtree" order.

For other information regarding in-order and pre-order, see http://en.wikipedia.org/wiki/Tree_traversal.