## Construct a full binary tree from preorder sequence with leaf node information

Write an efficient algorithm to construct a full binary tree from a sequence of keys representing preorder traversal, and a boolean array which determines if the corresponding key in the preorder traversal is a leaf node or an internal node.