Pre-order: F, B, A, D, C, E, G, I, H
p
In-order: A, B, C, D, E, F, G, H, I
q
From first char F in Pre-order, we are sure that the root of the tree is F.
and from In-order, F divide the tree into two parts, the left one is A, B, C, D, E, the right one is G, H, I.
F
/ \
A, B, C, D, E G, H, I
A, B, C, D, E and B, A, D, C, E become a new buildTree problem. so we can build the tree recursively.
the result tree is the left children of F.
Similarly, G, H, I and G, I, H become the right children of F.