这是预遍历算法：

Preorder(T)
  if (T is not null)
    print T.label
    Preorder(T.left)
    Preorder(T.right)

让我们尝试寻找输入的算法NNLLNL。

显然，首先打印了根标签。因此，您知道根目录具有label
N。现在该算法在左子树上递归。这也N根据输入。递归到它的左子树上L。现在您必须回溯，因为您已经到了一片空白。输入中的下一个位置也是L，因此当前节点有一个标记为的右孩子L。回溯一次。再次回溯，因为您已经添加了当前节点的所有子节点（最多2个子节点）。现在，您又回到了根。您必须向右走，因为您已经向左走。根据输入，这是N。因此，根的正确子是N。那的左孩子将是L。这是你的树：

       N
     /   \
    N     N
   / \   /
  L   L L

请注意，解决方案不一定是唯一的，但这将为您提供可能的解决方案。

伪代码：

k = 0
input = ... get preorder traversal vector from user ...
Reconstruct(T)
  if input[k] == N
    T = new node with label N
    k = k + 1 
    Reconstruct(T.left)
    Reconstruct(T.right)
  else 
    T = new node with label L
    T.left = T.right = null
    k = k + 1

用空节点调用。

后续问题 ：考虑到包含不同节点标签的二叉树的前序遍历和有序遍历，如何才能唯一地重建树？