有没有一种方法可以从严格二叉树的后序遍历中找到其先序遍历，而不需要构建整棵树？

Question

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

- fresh42juice

---

请问您能否举个例子，说明您正在处理的数据是什么？ - Har

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");

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

- M Oehm

---

啊！我默默地认为“严格的二叉树”指的是“没有重复值的二叉搜索树”。（我本来想问，但后来没问。）对此我深感抱歉。 - M Oehm

我现在已经完成了，并更新了我的答案。基本原则是相同的：存储最右边的节点，然后尝试找到左右子数组之间的边界在哪里。 - M Oehm

Answer 2

如果有能力重复阅读原始的后序表示，就可以使用O(N²)时间但恒定空间（一些计数器）将后序遍历转换为前序遍历。按顺序检查源的每个字符。如果它是一个节点，则丢弃它。如果它是一个叶子，则将“嵌套”计数器设置为零，并检查后续字符，对于每个叶子递增嵌套计数器，并对每个节点递减它。当到达源文本的末尾或值变为负时停止。输出那里的节点，然后反向工作到找到的叶节点，以与刚才所做的相反的方式递增和递减计数器。

计数器归零的每个位置都会立即跟随一个节点（如果没有，那就意味着在到达当前位置之前计数器已经变为负数）。输出该节点。一旦计数器到达了开始的叶节点，就输出它并丢弃它，因为它和它之前的任何东西都不再需要。

这种方法可能不像其他方法那样快，但它需要最少的内存，这可能对某些目的有利。

- supercat

Answer 3

如果您假设任何二叉树，而不是二叉搜索树，那么我认为不可能获得唯一的前序遍历序列。原因在于，您无法知道后序遍历序列中第二个、第三个等节点是左子树还是右子树的根节点。如果树是二叉搜索树，则很清楚，因为顺序将告诉您节点是在左子树还是右子树中。

如果您只想要一个与给定后序遍历序列对应的前序遍历序列，则可以假设一个从左侧不平衡的树。因此，简单地反转后序遍历序列就是左侧不平衡树的前序遍历序列。

例如，如果您的后序遍历序列是"abcd"，那么"dcba"是该树的有效前序遍历序列：

      d
     /
    c
   /
  b
 /
a

也许不是你想要的答案，但我认为这回答了你的陈述。

- lrleon