有没有办法在不构建树的情况下从后序遍历中找到严格二叉树的前序遍历？

Question

我得到了严格二叉树的后序遍历，并被要求找到它的前序遍历。通常，我会先构建树，然后找到前序遍历。但是，我想知道是否有任何方法可以在不实际构建树的情况下找到预序遍历。

Answer 1

[编辑：我首先回答这个问题，假设给定的后序来自严格排序的二叉搜索树。OP现在指出了我的错误并提供了一个例子。然而，两种算法的基本原理是相同的：找到左子树和右子树之间的边界在哪里。]

让我们考虑以下完整二叉树的后序遍历，其中每个节点要么是叶子，要么是具有两个叶子的分支：

1, 2, B, 3, 4, D, 5, C, A

我们知道数字是树叶，字母是树枝。我们还知道节点 A 是根，因为它在后序遍历中排在最后。为了重构前序遍历，我们必须存储根，然后考虑左子树，然后递归地考虑右子树。

但是哪些节点属于左子树，哪些属于右子树？在具有L 个叶子的满二叉树或严格二叉树中，有N = 2· L − 1 个节点。因此，在存储根之后，我们从右侧遍历剩余的子数组并跟踪节点数N和叶子数L。当考虑N = 2· L − 1 为真时，我们停止。我们看到的所有东西都属于右子树，其余的都属于左子树。

所以：

int is_leaf(int c)
{
    return !isalpha(c);     // non-alphas are leaves
}

void reconst(int **pre, const int *post, int lo, int hi)
{
    printf("%d :: %d\n", lo, hi);

    if (lo < hi) {
        int k = --hi;           // will be boundary between l/r
        int root = post[k];
        int leaves = 0;
        int nodes = 0;

        while (k > lo && nodes != 2 * leaves - 1) {
            if (is_leaf(post[k - 1])) leaves++;
            nodes++;
            k--;
        }

        *(*pre)++ = root;
        reconst(pre, post, lo, k);
        reconst(pre, post, k, hi);
    }
}

像这样称呼它：

int post[] = {'1', '2', 'B', '3', '4', 'D', '5', 'C', 'A'};
int n = 9;
int pre[9];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%c ", pre[i]);
}

puts("pre");

上面的代码依赖于以下几点： (a)数组必须与保存重构前序的数组pre一样大。post(b) 输入的格式必须正确。该算法依赖于找到正确的完整子树。（计数器被防止超出下限，但仅此而已。）

[原始帖子尝试从二叉搜索树的后序中查找前序，没有重复值，即严格排序。很好的答案，但因为误解了要求，而不是OP想要的。对于那个很抱歉。]

假设您得到如下的后序遍历：

3, 1, 7, 9, 8, 5

您知道顶部节点是 (5)，所有较小的节点 (3, 1) 都在左分支中，所有较大的节点 (7, 8, 9) 都在右分支中。前序遍历时，顶层节点先进入。这样做，然后递归代表左分支的子数组，然后递归代表右分支的子数组。

这是一个执行此操作的函数：

void reconst(int **pre, const int *post, int lo, int hi)
{
    if (lo < hi) {
        int k = --hi;                // k will be the boundary between l/r
        int parent = post[k];        // remove parent from this subarray

        // find boundary between left and right branches
        while (k > lo && post[k - 1] > parent) k--;

        *(*pre)++ = parent;          // write parent to pre-order array
        reconst(pre, post, lo, k);   // do the left subarray
        reconst(pre, post, k, hi);   // do the right subarray
    }
}

该pre数组通过指向指针的指针来填充：顶级指针跟踪数组中的位置pre，第二级指针访问底层数组。（您可以传递一个数组和一个索引，如果这太巴洛克式了，您可以将其提前。）

像这样调用该函数：

int post[] = {3, 1, 7, 9, 8, 5};
int n = 6;
int pre[6];
int *p = pre;
int i;

reconst(&p, post, 0, n);

for (i = 0; i < n; i++) {
    printf("%d ", pre[i]);
}

puts("pre");

当然，保存前序数据的数组必须与后序数组一样大。从后序数据重建树的代码看起来非常相似，所以我不知道这是否真的合格。