The idea of construction in fade2black's answer is correct (while the pseudocode may be buggy). I rewrite it here:
FOR i = 2 to n:
IF root.left is free:
root.left = make_node(n[i])
IF n[i] == 1:
root = root.left
# backtrack until root.right is free or we reach the ROOT - highest node
WHILE root is not nil AND root.right is not free:
root = root.parent
IF root is nil:
root.right = make_node(n[i])
IF n[i] == 1:
root = root.right
Its correctness can be proved by mathematical induction on $n$. Base cases are trivial.
Assume a sequence of length less than $n$ is valid if and only if a tree can be constructed by the algorithm. Now consider a sequence of length $n$.
If a tree can be constructed by the algorithm, the sequence is obviously valid.
On the other hand, if the sequence is valid, it must be $1, a_1,\ldots,a_p, b_1,\ldots,b_q$ where $a_1,\ldots, a_p$ and $b_1,\ldots,b_q$ are both valid sequences ($p$ or $q$ may be 0). By inductive assumption, the algorithm can construct a tree as the left subtree of the root from $a_1,\ldots,a_p$. Then the algorithm is handling $b_1$. Note the right child of the root is free, so the algorithm will not return "failure" during backtracking and successfully constructs $b_1$. By inductive assumption again, the algorithm sequentially constructs a subtree from $b_1,\ldots,b_q$. As a result, a tree is successfully constructed from the sequence $1,a_1,\ldots,a_p,b_1,\ldots,b_q$.