algorithm - 来自指定不存在子项的前序遍历的二叉树

Question

我有一个由前序遍历表示的二叉树，它看起来像这样：{1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }，其中 0 表示不存在元素的子元素。

如何从这些数据构造原始二叉树？我试图解决递归问题，但我还没有意识到如何处理节点的右子节点，因为我无法计算它们在数组中的位置，除非它们有一个叶子作为父节点（叶子有它后面的两个零，表示它没有孩子）。

我觉得解决方案必须非常简单，但仍然看不到它。

Answer 1

像这样简单的事情可能对你有用。您只需要在输入序列的预先解释中重新构建树。以下代码不验证输入序列以检查它是否是有效的树表示。

struct BTNode {
    int data;
    BTNode* left;
    BTNode* right;
}

BTNode* BuildTree(int* sequence, int& pos) {
    int value = sequence[pos++];
    if (value == 0)
        return nullptr;
    BTNode* node = new BTNode;
    node->data = value;
    node->left = BuildTree(sequence, pos);
    node->right = BuildTree(sequence, pos);
    return node;
}