这是预遍历算法：
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 = 0input = ... 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
用空节点调用。
后续问题 ：考虑到包含不同节点标签的二叉树的前序遍历和有序遍历，如何才能唯一地重建树？
